C Language, Different ways of implementing a 2d array

Different ways of implementing a 2d array

Author	Message
Thomas Stege #1 / 3	Different ways of implementing a 2d array If I want a two dimensional array there is essentially two ways of allcating memory. I would like some comments about which of the following methods you prefer. I think method 1 is the best way of doing things Error checking omitted for brevity. The code is only meant to demonstrate the general ideas and so there are quite a few things that can be done better. Method 1: Allocate memory for an array of pointers, then make each of those pointers point to allocated memory. Access is done through normal array indexing. #include <stdlib.h> int alloc2d(size_t cols, size_t rows) { int tmp = malloc(cols * sizeof tmp); int i = 0; for(i = 0;i < cols;i++) { tmp[i] = malloc(rows sizeof tmp[0]); } return tmp; Quote: } Method 2: Most of this would be wrapped up in struct of course, but the general idea should be clear. Use a single big array and calculate the offsets using a macro or function. #include <stdlib.h> size_t rows; size_t cols; /Use this macro to access the array/ #define ACCESS(arr, x, y) (((arr) + ((y) * cols) + (x))) int alloc2d(size_t col, size_t row) { int tmp = malloc(col * row * sizeof *tmp); rows = row; cols = col; return tmp; Quote: } -- Thomas
Thu, 07 Apr 2005 18:46:47 GMT

Simon Bibe #2 / 3	Different ways of implementing a 2d array Quote: > If I want a two dimensional array there is essentially two > ways of allcating memory. I would like some comments about > which of the following methods you prefer. I think method > 1 is the best way of doing things > Error checking omitted for brevity. The code is only meant to > demonstrate the general ideas and so there are quite a few > things that can be done better. > Method 1: > Allocate memory for an array of pointers, then make each of > those pointers point to allocated memory. Access is done > through normal array indexing. > #include <stdlib.h> > int alloc2d(size_t cols, size_t rows) > { > int tmp = malloc(cols * sizeof tmp); > int i = 0; > for(i = 0;i < cols;i++) > { > tmp[i] = malloc(rows sizeof tmp[0]); > } > return tmp; > } This requires lots of calls to malloc (cols + 1 calls). It's also tricky to back out without a memory leak if one of the calls to malloc fails somewhere in the loop. (You have to go back through the previous ones and free each one.) You can reduce the number of malloc calls to 2, and still have normal array-like indexing: int alloc2d(size_t cold, size_t rows) { int tmp = malloc(cols sizeof tmp); tmp[0] = malloc(cols rows * sizeof *tmp); for(i = 1; i < cols; i++) { tmp[i] = tmp[0] + i rows; } Quote: } > Method 2: > Most of this would be wrapped up in struct of course, > but the general idea should be clear. Use a single big > array and calculate the offsets using a macro or > function. > #include <stdlib.h> > size_t rows; > size_t cols; > /Use this macro to access the array/ > #define ACCESS(arr, x, y) (((arr) + ((y) cols) + (x))) Simplify it to: #define ACCESS(arr, x, y) ((arr)[(y) * cols + (x)]) Quote: > int alloc2d(size_t col, size_t row) > { > int tmp = malloc(col * row * sizeof *tmp); > rows = row; > cols = col; > return tmp; > } There's nothing wrong with this except the need to use the macro to access it according to your defined dimensions. -- Simon.
Thu, 07 Apr 2005 20:12:58 GMT

Andreas From #3 / 3	Different ways of implementing a 2d array Quote: > If I want a two dimensional array there is essentially two > ways of allcating memory. I would like some comments about > which of the following methods you prefer. I think method > 1 is the best way of doing things > Error checking omitted for brevity. The code is only meant to > demonstrate the general ideas and so there are quite a few > things that can be done better. > Method 1: > Allocate memory for an array of pointers, then make each of those > pointers point to allocated memory. Access is done through normal > array indexing. > #include <stdlib.h> > int alloc2d(size_t cols, size_t rows) > { > int tmp = malloc(cols * sizeof tmp); > int i = 0; > for(i = 0;i < cols;i++) > { > tmp[i] = malloc(rows sizeof tmp[0]); > } > return tmp; > } > Method 2: > Most of this would be wrapped up in struct of course, > but the general idea should be clear. Use a single big > array and calculate the offsets using a macro or > function. > #include <stdlib.h> > size_t rows; > size_t cols; > /Use this macro to access the array/ > #define ACCESS(arr, x, y) (((arr) + ((y) * cols) + (x))) > int alloc2d(size_t col, size_t row) > { > int tmp = malloc(col * row * sizeof tmp); > rows = row; > cols = col; > return tmp; > } > -- > Thomas Method 2 could be faster because of memory access speed. In Method 1 you have to fetch the address to the 2nd dimension array and then fetch the value you need, while in method 2 you just need to fetch the value at address _offset_. The evaluation of the offset should be faster then fetching pointers to pointers from memory. Method 1 has the advantage that it is more flexible. You can allocate just the rows you actually need, so you could save some memory in situations where you don't have entries in all rows, or you can even allocate just as many row entries as you need (you would need to take care of the index limits somewhere else). You can also implement non 0-aligned indexes. ip = (int) calloc ( 2maxX+1, sizeof( int* ) ) + maxX; for ( n = -maxX; n <= maxX; n++ ) (ip+n) = calloc ( 2maxY+1, sizeof( int ) ) + maxY; this would give you an array with indexes in the range ip(-maxX...maxX,-maxY...maxY). -- ************************************** Andreas Fromm
Fri, 08 Apr 2005 21:42:49 GMT

Page 1 of 1

[ 3 post ]