User Defined 2d Arrays

[jmw080]

I want to know how to malloc for a 2d array. I have the code for a single dimension array.

int size;
int* array;

array = (int*)malloc(si ze*sizeof(int)) ;

the user will input a number for 2 variables so size1 and size2. One amount for the columns and one for the rows. With the code above its only for one of these.

[kvbreddy]

Follow the link http://www-ee.eng.hawaii.edu/~tep/EE...on2.1.2.2.html

I want to know how to malloc for a 2d array. I have the code for a single dimension array.

int size;
int* array;

array = (int*)malloc(si ze*sizeof(int)) ;

the user will input a number for 2 variables so size1 and size2. One amount for the columns and one for the rows. With the code above its only for one of these.

[Ganon11]

I want to know how to malloc for a 2d array. I have the code for a single dimension array.

int size;
int* array;

array = (int*)malloc(si ze*sizeof(int)) ;

the user will input a number for 2 variables so size1 and size2. One amount for the columns and one for the rows. With the code above its only for one of these.

You can use a double pointer. The code will be, I think (I haven't used malloc):

int size1;
int size2;
int** array;

// Get sizes from user

array = (int**)malloc(size1 * sizeof(int*)); // Creates an array of int pointers
for (int i = 0; i < size1; i++)
   array[i] = (int*)malloc(size2 * sizeof(int)); // Each int* is an array of pointers

[AdrianH]

You can use a double pointer. The code will be, I think (I haven't used malloc):

int size1;
int size2;
int** array;

// Get sizes from user

array = (int**)malloc(size1 * sizeof(int*)); // Creates an array of int pointers
for (int i = 0; i < size1; i++)
   array[i] = (int*)malloc(size2 * sizeof(int)); // Each int* is an array of pointers

Yes this will work, and referencing is done like this:

array[i][j]

Where i is between 0 and size1-1 and j is between 0 and size2-1.

However, I think what kvbreddy was trying to get at is that you could use instead of a 2D array is a 1D array with a struct containing 2 elements. Depending on what your goal is, each has its uses.

The struct has no chance of overrunning the end of the array on the 2nd dimension, because there is no numerical index required, only members. If this is a concern, then a 1D array of a struct may be the answer.

2D arrays are only necessary if you are going to require indexing a cell in it given 2D coordinates.

Hope this helps.


Adrian

[willakawill]

I want to know how to malloc for a 2d array. I have the code for a single dimension array.

int size;
int* array;

array = (int*)malloc(si ze*sizeof(int)) ;

the user will input a number for 2 variables so size1 and size2. One amount for the columns and one for the rows. With the code above its only for one of these.

Hi. You don't need to use 2d arrays. You can do the same thing with 1d arrays using the following:

int cols = 10;
int rows = 20;
int i, j;
int answ;
int *ar = 0;

ar = (int*)malloc(cols*rows*sizeof(int));
for (i = 0; i<10; i++)
   for (j = 0; j<20; j++)
      answ = ar[i + (cols * j)];

[Ganon11]

You can use a 1d array, but that makes accessing elements very tedious - using array[i] from 0 to 254 instead of array[i][j] from 0 to 24, for example.

[AdrianH]

You can use a 1d array, but that makes accessing elements very tedious - using array[i] from 0 to 254 instead of array[i][j] from 0 to 24, for example.

I agree with Gannon11, if using a 1D array to house 2 elements per index, I'd recommend a struct unless your application requires a 2D array, in which case, don't do the job of the compiler. Its purpose is to try and make you life easier, not harder. :) Unless you are going to start casting to a 2D array type, then you are getting really advanced, and probably beyond what this person wants.


Adrian

[willakawill]

I agree with Gannon11, if using a 1D array to house 2 elements per index, I'd recommend a struct unless your application requires a 2D array, in which case, don't do the job of the compiler. Its purpose is to try and make you life easier, not harder. :) Unless you are going to start casting to a 2D array type, then you are getting really advanced, and probably beyond what this person wants.


Adrian

I can understand that the use of

ar[i + (cols * j)];

Seems so much more cumbersome than

ar[i][j];

when there does not appear to be any good reason for it.
In fact there is a big difference in how a single dimension and a 2d array are written to a binary file in a single pass as in ostream::write
Only single dimension binary files are compatible with vb binary input output for example
It is also much simpler to allocate memory for a single dimension as demonstrated and much more efficient particularly working with the array sizes I have in my current project.
Anyway, horses for courses. Whatever works :)

[nmadct]

It's true that a 1D array is more efficient than a 2D array, and the inefficiency of the 2D array increases with the size of the first index. For small arrays this probably isn't a big deal but it's good to know when you're making the decision. Here's a program that illustrates how you can build a 2D array from a 1D array, it will show how to do it and hopefully also help illustrate how 2D arrays work in C.

The program allocates a block of memory with one call to malloc, then constructs a 2D array in that space, with the cells containing numbers counting from 1 to 128. Then, it copies that array onto another block of memory that has already been initialized with all of its bits set. Finally, the results are printed from the second block of memory, and it then doubles back and prints the last integer in the allocated block.

The copying is done just to demonstrate that the numbers we've written exactly fill the space that was allocated. If we'd allocated too much memory then you'd see that when we print the last integer in the block, it's not the right value. If we'd allocated too little, then the end of the block wouldn't get copied at all. (If writing off the end of the allocated block didn't happen to crash your program already, that is.)

#include <stdio.h>
#include <memory.h>
#include <malloc.h>

int main()
{
        int i, j;
        int size = 16*sizeof(int*) + 8*16*sizeof(int);

        /* Allocate 2 blocks of memory. Give the
          second one some extra space. */
        int **original = (int**) malloc(size + 256);
        int **fresh = (int**) malloc(size + 256);

        if (original==NULL || fresh==NULL)
                return 1;

        int count = 1;
        for (i=0; i < 16; i++)
        {
                /* Make the first index values point to blocks
                  of the appropriate size */
                original[i] = (int*)(original + 16) + i*8;

                /* now fill in the numbers,
                  counting up 1 each time */
                for (j=0; j < 8; j++)
                {
                        original[i][j] = count;
                        count++;
                }
        }

        /* initialize the memory that fresh points to, then copy
           the contents of original into fresh */
        memset(fresh, 0xFF, size+256);
        memcpy(fresh, original, size);

        for (i=0; i < 16; i++)
        {
                /* have to set this pointers to point into THIS
                 block now */
                fresh[i] = (int*)(fresh + 16) + i*8;
                for (j=0; j < 8; j++)
                {
                        printf("%02d ", fresh[i][j]);
                }
                putchar('\n');
        }
        printf("Last number: %d\n",
          *((int*)((char*)original + size) - 1));
        return 0;
}

I'm pretty sure this program is correct for any platform and any version of C, but I'm not 100% sure. That's the other reason I did the copying part: to prove correctness. Once you start making assumptions about the way that a compiler handles pointers, you're usually heading into dangerous waters, although I think in this case you're safe because standard C requires this implementation of 2D arrays. If you do this kind of thing, at least make sure your comments explain what you were thinking!

[AdrianH]

I'm pretty sure this program is correct for any platform and any version of C, but I'm not 100% sure. That's the other reason I did the copying part: to prove correctness. Once you start making assumptions about the way that a compiler handles pointers, you're usually heading into dangerous waters, although I think in this case you're safe because standard C requires this implementation of 2D arrays. If you do this kind of thing, at least make sure your comments explain what you were thinking!

I've looked briefly at this and it is definitely interesting. You are using double pointers to simulate a 2D array (this is how C first did this) that is 16x8. There is defiantly nothing wrong with this, but you can see how much code you need to write and the potential for error in writing it. Because of the general pattern you are showing however, you are on your way to writing a general library for 2D arrays, so if you really want to do this right, you may want to setup an interface to create, access, copy and delete the array.

A few things I saw, that caught my eye that I found confusing were:

        int size = 16*sizeof(int*) + 8*16*sizeof(int);

I see where 16*sizeof(int*) came from, but where did 16 in 8*16*sizeof(int ) come from? The first 8 represents the number of elements in that dimention, the sizeof(int) represents the size of the int, but the 16?

        /* Allocate 2 blocks of memory. Give the
          second one some extra space. */
        int **original = (int**) malloc(size + 256);
        int **fresh = (int**) malloc(size + 256);

What are the additional 256 bytes for?

Also, if you wanted to, instead of using the older style of C arrays, you can use the newer ones that allow you to generate them on the stack. These are passed by reference and are more memory and possibly more processing efficient as they are allocated in one block with no intermediate pointers. Indexing to an element will cause a calculation to be made to determine the offset to the element in question.

But care must be taken when passing these arrays in C, since you may pass one with a different 2nd or higher dimension which would then make the compiler calculate the offset to the element that you are trying to indexing to incorrectly. This problem doesn't exist in C++ due to the strong type system it employs.

Here is an example of its usage:

#define SIZE_X1 10
#define SIZE_X2 20
#define SIZE_Y1  5
#define SIZE_Y2  6

/* NOTE: The first dimension can be variable as it doesn't change the offset       */
/*       calculation. However, you may run off the end of the 1st dimension without*/
/*       knowing the upper array bound.                                            */
void set(int array[][SIZE_Y1], int x, int y, int value)
{
  /* use array just like a regular array */
  array[x][y]=value;
}

int main()
{
  int array1[SIZE_X1][SIZE_Y1] = {}; /* The = {} means to have it initialise the */
  int array2[SIZE_X2][SIZE_Y1] = {}; /* array's elements to the default value.   */
  int array3[SIZE_X2][SIZE_Y2] = {}; /* For int's, that value is 0.              */
  set(array1, 1, 0, 9); /* Valid */
  set(array2, 1, 0, 9); /* Valid */
  set(array3, 1, 0, 9); /* Invalid, but would compile under C with wrong results */
                        /* Will not compile under C++ due to strong typing. */
  return 0;
}

One could pass the dimension of the array to get the compiler to calculate the correct offset, but this notation is valid only in C, not C++, and allows you to pass the wrong dimensional size.

#define SIZE_X1 10
#define SIZE_X2 20
#define SIZE_Y1  5
#define SIZE_Y2  6

/* NOTE: The first dimension can be variable as it doesn't change the offset       */
/*       calculation. However, you may run off the end of the 1st dimension without*/
/*       knowing the upper array bound.                                            */
/* NOTE: This notation (specifying size of array by preceding variable dimension)  */
/*       is valid only in C.                                                       */
void set(int sizeY, int array[][sizeY], int x, int y, int value)
{
  /* use array just like a regular array */
  array[x][y]=value;
}

int main()
{
  int array1[SIZE_X1][SIZE_Y1] = {}; /* The = {} means to have it initialise the */
  int array2[SIZE_X2][SIZE_Y1] = {}; /* array's elements to the default value.  */
  int array3[SIZE_X2][SIZE_Y2] = {}; /* For int's, that value is 0 */
  set(SIZE_Y1, array1, 1, 0, 9);   /* Valid */
  set(SIZE_Y1, array2, 1, 0, 9);   /* Valid */
  set(SIZE_Y2, array3, 1, 0, 9);   /* Valid */
  set(SIZE_Y2+1, array3, 1, 0, 9); /* invalid but will compile with wrong results */
  return 0;
}

To make this work under C++, use a template which is far safer than the C version:

#define SIZE_X1 10
#define SIZE_X2 20
#define SIZE_Y1  5
#define SIZE_Y2  6

/* NOTE: The first dimension can be variable as it doesn't change the offset       */
/*       calculation. However, you may run off the end of the 1st dimension without*/
/*       knowing the upper array bound.                                            */
/* NOTE: Templates are valid only in C++.                                          */
template<int sizeY>
void set(int array[][sizeY], int x, int y, int value)
{
  /* use array just like a regular array */
  array[x][y]=value;
}

int main()
{
  int array1[SIZE_X1][SIZE_Y1] = {}; /* The = {} means to have it initialise the */
  int array2[SIZE_X2][SIZE_Y1] = {}; /* array's elements to the default value.  */
  int array3[SIZE_X2][SIZE_Y2] = {}; /* For int's, that value is 0 */
  set(array1, 1, 0, 9);   /* Valid */
  set(array2, 1, 0, 9);   /* Valid */
  set(array3, 1, 0, 9);   /* Valid */
  return 0;
}

One thing I have not figured out yet with these types of multi-dimensional arrays is if you can pass it back from a function, if you can create on of these on the heap and point at it, or if you can cast to one. If anyone has any answers to these questions, please post.

Oh and under C99 standard, you can also declare the array without the dimensions being a constant (i.e. make a dynamic array). However, the easy initialisation doesn’t work. This is probably because if you specified the actual contents of the array how is the compiled programme to respond if the dynamic array size is smaller than the initialisers specified? So you have to initialise the array yourself. g++ allows for dynamic arrays as well, but it is a gnu extension and not part of the current C++ spec.

/* NOTE: The first dimension can be variable as it doesn't change the offset       */
/*       calculation. However, you may run off the end of the 1st dimension without*/
/*       knowing the upper array bound.                                            */
void set(int array[][SIZE_Y1], int x, int y, int value)
{
  /* use array just like a regular array */
  array[x][y]=value;
}

int main()
{
  int sizeX1 = 10;
  int sizeX2 = 20;
  int sizeY1 = 5;
  int array1[sizeX1][sizeY1]; /* The = {} doesn’t work for dynamically    */
  int array2[sizeX2][sizeY1]; /* allocated arrays.                        */
  set(array1, 1, 0, 9); /* Valid */
  set(array2, 1, 0, 9); /* Valid */
  return 0;
}

Boy, I certainly learned a lot from what I just said. :) Some of that I had to test and research as I didn’t actually know all of that when I started.


Adrian

[nmadct]

A few things I saw, that caught my eye that I found confusing were:

        int size = 16*sizeof(int*) + 8*16*sizeof(int);

I see where 16*sizeof(int*) came from, but where did 16 in 8*16*sizeof(int ) come from? The first 8 represents the number of elements in that dimention, the sizeof(int) represents the size of the int, but the 16?

The first part is a list of 16 pointers.
The second part is a 16x8 matrix containing the actual integer values. That's where this comes from: 8*16*sizeof(int )

        /* Allocate 2 blocks of memory. Give the
          second one some extra space. */
        int **original = (int**) malloc(size + 256);
        int **fresh = (int**) malloc(size + 256);

What are the additional 256 bytes for?

The additional 256 isn't necessary. It's just there because I was hypothesizing that my method might not be correct, and if that's the case then my array might take up more space than the memory I allocated. I didn't actually expect that to happen, though. The testing mechanism allows the correctness to be demonstrated with a few small tweaks to the code, however.

Also, if you wanted to, instead of using the older style of C arrays, you can use the newer ones that allow you to generate them on the stack. These are passed by reference and are more memory and possibly more processing efficient as they are allocated in one block with no intermediate pointers. Indexing to an element will cause a calculation to be made to determine the offset to the element in question.

That's very convenient, didn't know that.

Thanks, I learned some stuff from your post also.

[AdrianH]

The first part is a list of 16 pointers.
The second part is a 16x8 matrix containing the actual integer values. That's where this comes from: 8*16*sizeof(int )


The additional 256 isn't necessary. It's just there because I was hypothesizing that my method might not be correct, and if that's the case then my array might take up more space than the memory I allocated. I didn't actually expect that to happen, though. The testing mechanism allows the correctness to be demonstrated with a few small tweaks to the code, however.

Ahh, I definatly see what you did. Definatly better to put into a set of functions. Too easy to screw it up. I wrote one library set, but I just realised that I probably shouldn't post it. I don't think I we are allowed post the code to answer the question. What Ganon11 did in post 3 was to clear up the syntax, not show a general library. We are not here to do other people's (possibly students) work.

So to get back to the original question:

I want to know how to malloc for a 2d array. I have the code for a single dimension array.

int size;
int* array;

array = (int*)malloc(si ze*sizeof(int)) ;

the user will input a number for 2 variables so size1 and size2. One amount for the columns and one for the rows. With the code above its only for one of these.

Ganon11 post 3 in this thread was correct, sweet and simple.


Adrian

[jmw080]

Thank all of you for your help. Now that i have a better understanding of this i know what to do : ) The reason i was using a 2d array was because i did have to use a coordinate system for plotting data. I was just trying to save memory by allowing the user to define the space needed rather than making a very large element so that i would never have an overflow.

[Ganon11]

Glad to see you got it!

[AdrianH]

Great. Glad to be of service.


Adrian