Designation of rows and columns in a 2D dynamic array

Question

The following listing creates a 2D dynamic array.

#include <iostream>

#define COLS 3
#define ROWS 3

int ** create2d()
{
    int index = 1;
    int** arr = new int*[COLS];
    for (size_t i = 0; i < COLS ; i++)
    {
        arr[i] = new int[ROWS];
        for (size_t j = 0; j < ROWS ; j++)
        {
            arr[i][j] = index++;
            printf("%d (%d) [%d][%d]\t", arr[i][j], &arr[i][j], i,j);
        }
      printf("\n");
    }
  
    return arr;
}

int main()
{
    int** arr = create2d();
    for (int i = 0; i < COLS; i++) 
    {
        delete[] arr[i];
    }
    delete[] arr;
    return 0;
}

Output

./main
1 (34979536) [0][0] 2 (34979540) [0][1] 3 (34979544) [0][2]
4 (34980608) [1][0] 5 (34980612) [1][1] 6 (34980616) [1][2]
7 (34980640) [2][0] 8 (34980644) [2][1] 9 (34980648) [2][2]

From the output, we see that the increment of the elements and addresses of the elements of the array match.

Are the COLS and ROWS designations correct?

If so, does that mean that in arr[p][q] the left hand index (p) can be always considered as column and right hand index (q) can always be considered as row?

Answer 1

Everytime you output '\n' you are ending a row. The inner loop, therefore, prints the elements of one row. To do that, the column index must range between 0 and what I call n_cols. You hold the row index constant, and vary the column index. Therefore the thing you call ROWS is actually n_cols.

Each iteration of the outer loop prints one row. How many rows do you print? I would call that n_rows, but you have labeled it COLS.

So I would say, no, your designations of ROWS and COLS are not correct.

If you change COLS to 2, but keep ROWS at 3, your output will contain two rows, not two columns.

You suggest that your j index is a row index, but you print it second, where it is normal to print the column index. Basically, you've transposed names just enough to convince yourself that the matrix is stored in column-major order.

Answer 2

Why do we say that arrays are stored in row-major order in C and C++?

In mathematics, the conventional order for subscripts in a two-dimensional matrix it to put the row subscript first, followed by the column subscript. For a given matrix A, the element in row m and column n is denoted A(m,n). It is this convention that will force us to conclude that two-dimensional arrays in C and C++ are stored in row-major order.

Of course, in C and C++, there are no actual two-dimensional arrays. The closest analog is an array of arrays. That is what we mean when we say "two-dimensional array."

In the declaration below, A is such an array. Its type is array of arrays of int.

enum : std::size_t { M = 3, N = 2 };
int A[M][N]; 

More precisely, its type is "array of M elements, where each element is an array of N elements of type int." Whew! That's a mouthful.

Here are a few type aliases that spell it out:

enum : std::size_t { M = 3, N = 2 };
using array_of_N_ints 
    = int[N];
using array_of_M_arrays_of_N_ints 
    = array_of_N_ints[M];
using M_by_N_matrix 
    = array_of_M_arrays_of_N_ints;
M_by_N_matrix A;

The type M_by_N_matrix is the same as int[M][N]. You can test that, using std::is_same_v in a program.

The elements of an M_by_N_matrix are referenced using the bracket operator[] twice, e.g. A[m][n]. The rules for operator[] mandate a left-to-right binding order, so this is equivalent to (A[m])[n]. The meaning is "the nth element of array A[m], where A[m] is the mth element of array A." Another mouthful!

Now we see why subscript m is associated with rows: we want A[m][n] in C and C++ to mean the same thing as A(m,n) in mathemetics. The first subscript is the row subscript. It's a convention, and nothing more.

Okay, so how do we get to row-major order?

The answer lies is the definition of arrays. The elements of an array are mandated to be stored in contiguous locations (possibly with padding added to satisfy alignment requirements). Element 0 is stored first, followed by element 1, and so on.

In the example above, the elements of array A are are arrays. Because M = 3, there are three of them. They are stored consecutively:

A[0] A[1] A[2]

But we decided above that the first subscript is a row subscript. A[0] is an array of N ints that corresponds to row 0 in our mathematical matrix. Similarly, A[1] is row 1, and A[2] is row 2. This is row-major order, by definition.

row0 row1 row2

So there you have it: A "two-dimensional array" is stored in row-major order in both C and C++.

By the way, the program below returns 0.

#include <cstddef>
#include <type_traits>
int main()
{
    enum : std::size_t { M = 3, N = 2 };
    using array_of_N_ints 
        = int[N];
    using array_of_M_arrays_of_N_ints 
        = array_of_N_ints[M];
    using M_by_N_matrix 
        = array_of_M_arrays_of_N_ints;
    M_by_N_matrix A;
    return std::is_same_v<M_by_N_matrix, int[M][N]> ? 0 : 1;
}