Map a 2D array onto a 1D array

Question

I want to represent a 2D array with a 1D array. A function will pass the two indicies (x,y) and the value to store. These two indicies would represent a single element of a 1D array, and set it accordingly. I know the 1D array needs to have the size of arrayWidth × arrayHeight, but I don't know how to set each element.

For example, how do I distinguish (2,4,3) from (4,2,3)? I tried setting the array as the x*y, but 2*4 and 4*2 would result in the same spot in the array and I need them to be different.

Answer 1

It's important to store the data in a way that it can be retrieved in the languages used. C-language stores in row-major order (all of first row comes first, then all of second row,...) with every index running from 0 to it's dimension-1. So the order of array x[2][3] is x[0][0], x[0][1], x[0][2], x[1][0], x[1][1], x[1][2]. So in C language, x[i][j] is stored the same place as a 1-dimensional array entry x1dim[ i*3 +j]. If the data is stored that way, it is easy to retrieve in C language.

Fortran and MATLAB are different. They store in column-major order (all of first column comes first, then all of second row,...) and every index runs from 1 to it's dimension. So the index order is the reverse of C and all the indices are 1 greater. If you store the data in the C language order, FORTRAN can find X_C_language[i][j] using X_FORTRAN(j+1, i+1). For instance, X_C_language[1][2] is equal to X_FORTRAN(3,2). In 1-dimensional arrays, that data value is at X1dim_C_language[2*Cdim2 + 3], which is the same position as X1dim_FORTRAN(2*Fdim1 + 3 + 1). Remember that Cdim2 = Fdim1 because the order of indices is reversed.

MATLAB is the same as FORTRAN. Ada is the same as C except the indices normally start at 1. Any language will have the indices in one of those C or FORTRAN orders and the indices will start at 0 or 1 and can be adjusted accordingly to get at the stored data.

Sorry if this explanation is confusing, but I think it is accurate and important for a programmer to know.

Answer 2

using row major example:

A(i,j) = a[i + j*ld]; // where ld is the leading dimension
                      // (commonly same as array dimension in i)

// matrix like notation using preprocessor hack, allows to hide indexing
#define A(i,j) A[(i) + (j)*ld]

double *A = ...;
size_t ld = ...;
A(i,j) = ...;
... = A(j,i);

Answer 3

You should be able to access the 2d array with a simple pointer in place. The array[x][y] will be arranged in the pointer as p[0x * width + 0y][0x * width + 1y]...[0x * width + n-1y][1x * width + 0y] etc.

Answer 4

You need to decide whether the array elements will be stored in row order or column order and then be consistent about it. http://en.wikipedia.org/wiki/Row-major_order

The C language uses row order for Multidimensional arrays

To simulate this with a single dimensional array, you multiply the row index by the width, and add the column index thus:

 int array[width * height];

 int SetElement(int row, int col, int value)
 {
    array[width * row + col] = value;  
 }

Answer 5

The typical formula for recalculation of 2D array indices into 1D array index is

index = indexX * arrayWidth + indexY;

Alternatively you can use

index = indexY * arrayHeight + indexX;

(assuming that arrayWidth is measured along X axis, and arrayHeight along Y axis)

Of course, one can come up with many different formulae that provide alternative unique mappings, but normally there's no need to.

In C/C++ languages built-in multidimensional arrays are stored in memory so that the last index changes the fastest, meaning that for an array declared as

int xy[10][10];

element xy[5][3] is immediately followed by xy[5][4] in memory. You might want to follow that convention as well, choosing one of the above two formulae depending on which index (X or Y) you consider to be the "last" of the two.

Answer 6

As other have said C maps in row order

   #include <stdio.h>

   int main(int argc, char **argv) {
   int i, j, k;
   int arr[5][3];
   int *arr2 = (int*)arr;

       for (k=0; k<15; k++) {
          arr2[k] = k;
          printf("arr[%d] = %2d\n", k, arr2[k]);
       }

       for (i=0; i<5; i++) {
         for (j=0; j< 3; j++) {
            printf("arr2[%d][%d] = %2d\n", i, j ,arr[i][j]);
         }
       } 
    } 

Output:

arr[0] =  0
arr[1] =  1
arr[2] =  2
arr[3] =  3
arr[4] =  4
arr[5] =  5
arr[6] =  6
arr[7] =  7
arr[8] =  8
arr[9] =  9
arr[10] = 10
arr[11] = 11
arr[12] = 12
arr[13] = 13
arr[14] = 14
arr2[0][0] =  0
arr2[0][1] =  1
arr2[0][2] =  2
arr2[1][0] =  3
arr2[1][1] =  4
arr2[1][2] =  5
arr2[2][0] =  6
arr2[2][1] =  7
arr2[2][2] =  8
arr2[3][0] =  9
arr2[3][1] = 10
arr2[3][2] = 11
arr2[4][0] = 12
arr2[4][1] = 13
arr2[4][2] = 14