array offset calculations in multi dimensional array (column vs row major)

Question

A textbook I recently read discussed row major & column major arrays. The book primarily focused on 1 and 2 dimensional arrays but didn't really discuss 3 dimensional arrays. I'm looking for some good examples to help solidify my understanding of addressing an element within a multi-dimensional array using row major & column major arrays.

            +--+--+--+  |           /  /  /  /|  |          +--+--+--+ +  |        +---+---+---+---+         /  /  /  /|/|  |       /   /   /   /   /|        +--+--+--+ + +  |      +---+---+---+---+ +       /  /  /  /|/|/|  |     /   /   /   /   /|/|      +--+--+--+ + + +  |    +---+---+---+---+ + +     /  /  /  /|/|/|/|  |   /   /   /   /   /|/|/|    +--+--+--+ + + + +  |  +---+---+---+---+ + + +   /  /  /  /|/|/|/|/   |  |000|001|002|003|/|/|/|  +--+--+--+ + + + +    |  +---+---+---+---+ + + +  |00|01|02|/|/|/|/     |  |004|005|006|007|/|/|/|  +--+--+--+ + + +      |  +---+---+---+---+ + + +  |03|04|05|/|/|/       |  |008|009|00A|00B|/|/|/  +--+--+--+ + +        |  +---+---+---+---+ + +  |06|07|08|/|/         |  |00C|00D|00E|00F|/|/  +--+--+--+ +          |  +---+---+---+---+ +  |09|0A|0B|/           |  |010|011|012|013|/  +--+--+--+            |  +---+---+---+---+  arr[5][3][4]          |    arr[3][4][5] 

NOTE: Original question incorrectly represented arr[3][4][5]. I have learned that the original subscript represents depth. The data has been corrected to reflect intended array representation.

 Example hex data  +---+---+---+---+  +---+---+---+---+  +---+---+---+---+      |000|001|002|003|  |100|101|102|103|  |200|201|202|203|    +---+---+---+---+  +---+---+---+---+  +---+---+---+---+    |004|005|006|007|  |104|105|106|107|  |204|205|206|207|     +---+---+---+---+  +---+---+---+---+  +---+---+---+---+     |008|009|00A|00B|  |108|109|10A|10B|  |208|209|20A|20B|     +---+---+---+---+  +---+---+---+---+  +---+---+---+---+     |00C|00D|00E|00F|  |10C|10D|10E|10F|  |20C|20D|20E|20F|  +---+---+---+---+  +---+---+---+---+  +---+---+---+---+   |010|011|012|013|  |110|111|112|113|  |210|211|212|213|  +---+---+---+---+  +---+---+---+---+  +---+---+---+---+        slice 0            slice 1            slice 2   short Arr[3][4][5]; // assume array is filled with hex test data   arr[1][2][3] = 0x10B use slice 1, row 2, col 3  arr[2][3][4] = 0x210 use slice 2, row 3, col 4                         resolves to row 4, col 0  

row major
{000,001,002,003,004,005,006,007,008,009,00A,00B,00C,00D,00E,00F,010,011,012,013, 100,101,102,103,104,105,106,107,108,109,10A,10B,10C,10D,10E,10F,110,111,112,113, 200,201,202,203,204,205,206,207,208,209,20A,20B,20C,20D,20E,20F,210,211,212,213}

column major {000,004,008,00C,010,001,005,009,00D,011,002,006,00A,00E,012,003,007,00B,00F,013, 100,104,108,10C,110,101,105,109,10D,111,102,106,10A,10E,112,103,107,10B,10F,113, 200,204,208,20C,210,201,205,209,20D,211,202,206,20A,20E,212,203,207,20B,20F,213}

   Calculation offset for arr[1][2][3] using row major offset?   Calculation offset for arr[1][2][3] using column major offset? 

Answer 1

Don't artificially constrain yourself by focusing on 3-dimensional and 2-dimensional. Instead focus on learning the expression for addressing n-dimensional arrays.

Expressing n-dimensional addressing would solidfy your grasp on this subject and will be easier to remember one formula rather than separate formulas for 2d and 3d addressing.

---

Here's my attempt at n-dimensional addressing:

#define LEN 10  int getValue_nDimensions( int * baseAddress, int * indexes, int nDimensions ) {     int i;     int offset = 0;     for( i = 0; i < nDimensions; i++ ) {         offset += pow(LEN,i) * indexes[nDimensions - (i + 1)];     }      return *(baseAddress + offset); }  int main() {     int i;     int * baseAddress;     int val1;     int val2;      // 1 dimensions     int array1d[LEN];     int array1d_indexes[] = {2};     int array1d_nDimensions = 1;     baseAddress = &array1d[0];     for(i = 0; i < LEN; i++) { baseAddress[i] = i; }     val1 = array1d[2];     val2 = getValue_nDimensions( // Equivalent to: val1 = array1d[2];         baseAddress,         &array1d_indexes[0],         array1d_nDimensions     );     printf("SANITY CHECK: %d %d\n",val1,val2);      // 3 dimensions     int array3d[LEN][LEN][LEN];     int array3d_indexes[] = {2,3,4};     int array3d_nDimensions = 3;     baseAddress = &array3d[0][0][0];     for(i = 0; i < LEN*LEN*LEN; i++) { baseAddress[i] = i; }     val1 = array3d[2][3][4];     val2 = getValue_nDimensions( // Equivalent to: val1 = array3d[2][3][4];         baseAddress,         &array3d_indexes[0],         array3d_nDimensions     );     printf("SANITY CHECK: %d %d\n",val1,val2);      // 5 dimensions     int array5d[LEN][LEN][LEN][LEN][LEN];     int array5d_indexes[] = {2,3,4,5,6};     int array5d_nDimensions = 5;     baseAddress = &array5d[0][0][0][0][0];     for(i = 0; i < LEN*LEN*LEN*LEN*LEN; i++) { baseAddress[i] = i; }     val1 = array5d[2][3][4][5][6];     val2 = getValue_nDimensions( // Equivalent to: val1 = array5d[2][3][4][5][6];         baseAddress,         &array5d_indexes[0],         array5d_nDimensions     );     printf("SANITY CHECK: %d %d\n",val1,val2);      return 0; } 

Output:

SANITY CHECK:     2     2 SANITY CHECK:   234   234 SANITY CHECK: 23456 23456 

Answer 2

I would see the Row-major order Wikipedia article. There is a section that described dimensions higher than 2. There is also a good article here. That article gives the following formula for a three-dimensional array using a row-major layout:

Address = Base + ((depthindex*col_size+colindex) * row_size + rowindex) * Element_Size 

For a 3D array: type A[depth][col][row]. The base is the starting offset of the array. In addition, the size variables are the different sizes of each dimension. The Element_Size variable denotes the size of whatever type the array is composed of.

Suppose you had row-major array a[4][6][5] composed of standard C++ integers. To compute the offset of a[1][3][2], you would plug the following numbers into the formula:

Address = Base + ((1 * 6 + 3) * 5 + 2) * 4 

For a 3 dimensional array that has a column-major layout, the equation would rather be this:

Address = Base + ((rowindex*col_size+colindex) * depth_size + depthindex) * Element_Size 

The numbers you would plug in for the example above using a column-major layout would now be this:

Address = Base + ((2 * 6 + 3) * 4 + 1) * 4