dynamically size multidimensional arrays in C/C++

A place to discuss the implementation and style of computer programs.

Moderators: phlip, Moderators General, Prelates

webb.am
Posts: 41
Joined: Wed Feb 24, 2010 1:09 pm UTC

dynamically size multidimensional arrays in C/C++

Postby webb.am » Fri Feb 26, 2010 3:49 pm UTC

Has anyone else noticed how awful C is for dynamically sized arrays?

One dimension is fine. In C++ you can do:

Code: Select all

const int a=10;
const int b=20;
 int* exampleArray = new int[a];
.
.
.
delete exampleArray;
exampleArray = new int[b];


Now, to me, it seems like common sense that you should be able to do:

Code: Select all

const int a=10;
const int b=20;
int* exampleArray = new int[a][a];
.
.
.
delete exampleArray;
exampleArray = new int[b][b];


... but you can't. I can only think of one way around this:

Code: Select all

const int a=10;
int** exampleArray = new int*[a];
for(int i=0; i<a; i++)
    exampleArray[i] = new int[a];


I don't like this solution. The array is messy to create, messy to resize and messy to remove. It's horrible for higher dimensions.

Does anyone have a neater solution? (I know 2D vectors can be easier to work with, but they're not always ideal)

fazzone
Posts: 186
Joined: Wed Dec 10, 2008 9:38 pm UTC
Location: A boat

Re: dynamically size multidimensional arrays in C/C++

Postby fazzone » Fri Feb 26, 2010 4:29 pm UTC

As far as I know, there is no more elegant solution. The alternative is to use a one-dimensional array, and manually do the pointer arithmetic.

Edit: If you want the new int[n][n] syntax, use Java.
*/

User avatar
Xeio
Friends, Faidites, Countrymen
Posts: 5101
Joined: Wed Jul 25, 2007 11:12 am UTC
Location: C:\Users\Xeio\
Contact:

Re: dynamically size multidimensional arrays in C/C++

Postby Xeio » Fri Feb 26, 2010 6:45 pm UTC

fazzone wrote:Edit: If you want the new int[n][n] syntax, use Java.
And if you want the [n,n] syntax use C#. :P

User avatar
You, sir, name?
Posts: 6983
Joined: Sun Apr 22, 2007 10:07 am UTC
Location: Chako Paul City
Contact:

Re: dynamically size multidimensional arrays in C/C++

Postby You, sir, name? » Fri Feb 26, 2010 7:29 pm UTC

webb.am wrote:Has anyone else noticed how awful C is for dynamically sized arrays?


How so? What's wrong with

Code: Select all

int (*foo)[n][m] = malloc(m*n*sizeof(int);
(*foo)[x][y] = 123;
free(foo);


You created a one-dimensional array of pointers, not a pointer to a 2-dimensional array.
I edit my posts a lot and sometimes the words wrong order words appear in sentences get messed up.

User avatar
TNorthover
Posts: 191
Joined: Wed May 06, 2009 7:11 am UTC
Location: Cambridge, UK

Re: dynamically size multidimensional arrays in C/C++

Postby TNorthover » Fri Feb 26, 2010 9:31 pm UTC

You, sir, name? wrote:
webb.am wrote:Has anyone else noticed how awful C is for dynamically sized arrays?

How so? What's wrong with

It becomes problematic if you want to use any of this new-fangled procedural programming. Though I suppose passing dimensions manually and some dodgy casting could get around that.

User avatar
You, sir, name?
Posts: 6983
Joined: Sun Apr 22, 2007 10:07 am UTC
Location: Chako Paul City
Contact:

Re: dynamically size multidimensional arrays in C/C++

Postby You, sir, name? » Fri Feb 26, 2010 9:39 pm UTC

TNorthover wrote:
You, sir, name? wrote:
webb.am wrote:Has anyone else noticed how awful C is for dynamically sized arrays?

How so? What's wrong with

It becomes problematic if you want to use any of this new-fangled procedural programming. Though I suppose passing dimensions manually and some dodgy casting could get around that.


If you absolutely want to pass an arbitrarily-dimensioned array to a function , you could always just send it as a void*. This is C we're speaking of, after all.
I edit my posts a lot and sometimes the words wrong order words appear in sentences get messed up.

0rm
Posts: 81
Joined: Wed Feb 17, 2010 2:30 pm UTC

Re: dynamically size multidimensional arrays in C/C++

Postby 0rm » Fri Feb 26, 2010 9:48 pm UTC

Multidimensional Vector? You could do something like

Code: Select all

std::vector<std::vector<type>> multidim_vector;
// then call it like
int my_int = multidim_vector[1][5];


Give it a try.
They say it's unhackable; I think it can be hacked.
They say it's fast; I think it could be faster.
They say it's the best; I think it can be done better.

User avatar
Cosmologicon
Posts: 1806
Joined: Sat Nov 25, 2006 9:47 am UTC
Location: Cambridge MA USA
Contact:

Re: dynamically size multidimensional arrays in C/C++

Postby Cosmologicon » Fri Feb 26, 2010 11:03 pm UTC

In C++ you should make a class and overload the subscript operator. The C++ FAQ has some info on this topic.

Osha
Posts: 727
Joined: Wed Dec 03, 2008 3:24 am UTC
Location: Boise, Idaho, USA

Re: dynamically size multidimensional arrays in C/C++

Postby Osha » Fri Feb 26, 2010 11:10 pm UTC

I tend to do it the quick and dirty way, simulating a higher dimensional array with a 1D array and a bit of math.
for 2D:

Code: Select all

array[LENGTH*y+x];

and I even did it for 3D once, though I forget how that goes.

User avatar
You, sir, name?
Posts: 6983
Joined: Sun Apr 22, 2007 10:07 am UTC
Location: Chako Paul City
Contact:

Re: dynamically size multidimensional arrays in C/C++

Postby You, sir, name? » Fri Feb 26, 2010 11:17 pm UTC

Osha wrote:I tend to do it the quick and dirty way, simulating a higher dimensional array with a 1D array and a bit of math.
for 2D:

Code: Select all

array[LENGTH*y+x];

and I even did it for 3D once, though I forget how that goes.


For an arbitrary-dimensional array:

x + X*(y + Y*(z + Z*(w + ... ) ) )

Where X, Y, Z, ... is the limit of x,y,z, ...
I edit my posts a lot and sometimes the words wrong order words appear in sentences get messed up.

User avatar
headprogrammingczar
Posts: 3072
Joined: Mon Oct 22, 2007 5:28 pm UTC
Location: Beaming you up

Re: dynamically size multidimensional arrays in C/C++

Postby headprogrammingczar » Sat Feb 27, 2010 12:25 am UTC

In C++, you can use a Vector<Vector*>, or however deep you want it. Just be sure to use indexes to access data, rather than pointers, since iirc, it uses realloc to increase in size.
<quintopia> You're not crazy. you're the goddamn headprogrammingspock!
<Weeks> You're the goddamn headprogrammingspock!
<Cheese> I love you

User avatar
Cosmologicon
Posts: 1806
Joined: Sat Nov 25, 2006 9:47 am UTC
Location: Cambridge MA USA
Contact:

Re: dynamically size multidimensional arrays in C/C++

Postby Cosmologicon » Sat Feb 27, 2010 1:20 am UTC

headprogrammingczar wrote:In C++, you can use a Vector<Vector*>, or however deep you want it. Just be sure to use indexes to access data, rather than pointers, since iirc, it uses realloc to increase in size.

You can even initialize the whole thing without a loop! I think this is right for a 3-D array:

Code: Select all

  vector<vector<vector<int> > > a(x, vector<vector<int> >(y, vector<int>(z, 0)));

cogman
Posts: 112
Joined: Sun May 18, 2008 2:17 pm UTC

Re: dynamically size multidimensional arrays in C/C++

Postby cogman » Sat Feb 27, 2010 4:01 am UTC

Consider this, at the low level, all arrays are basically 1d, the difference is in how they are interpreted. If you would like a n x n x n x n dynamic array, then you could just do something to the effect of

int**** 4darray = (int****)(new int[n * n * n * n]);

That will create an n x n x n x n array that you could access normally as 4darray[1][2][3][4].

Enjoy.

Osha
Posts: 727
Joined: Wed Dec 03, 2008 3:24 am UTC
Location: Boise, Idaho, USA

Re: dynamically size multidimensional arrays in C/C++

Postby Osha » Sat Feb 27, 2010 4:25 am UTC

That code compiles fine but segfaults as either C or C++

Spoiler:

Code: Select all

#include <stdio.h>
#include <stdlib.h>

int main(int argc,char** argv) {
 #ifdef __cplusplus
    int**** _4darray = (int****)(new int[10 * 10 * 10 * 10]);
#else
    int**** _4darray = (int****)(malloc(sizeof(int) *10 * 10 * 10 * 10));
#endif

    _4darray[1][2][3][4] = 7;
    printf("value: %d\n",_4darray[1][2][3][4]);
    return 0;
}

Segmentation fault (core dumped)

User avatar
Xeio
Friends, Faidites, Countrymen
Posts: 5101
Joined: Wed Jul 25, 2007 11:12 am UTC
Location: C:\Users\Xeio\
Contact:

Re: dynamically size multidimensional arrays in C/C++

Postby Xeio » Sat Feb 27, 2010 4:48 am UTC

cogman wrote:int****
I hate you. :P

Also, here. Boost is your friend, seriously.
Last edited by Xeio on Sat Feb 27, 2010 8:48 pm UTC, edited 1 time in total.

Rysto
Posts: 1460
Joined: Wed Mar 21, 2007 4:07 am UTC

Re: dynamically size multidimensional arrays in C/C++

Postby Rysto » Sat Feb 27, 2010 5:03 am UTC

In C++ use Boost.

I am pretty much certain that the dynamic code already posted does not work. int ** means pointer to pointer to int, not two-dimensional array of int. If you consider the expression array[0], this will return the first piece of memory that you allocated. So the expression array[0][1] means "take the value at array[0], treat it as a pointer to an array and return the value at index 1 of that array.

User avatar
Sc4Freak
Posts: 673
Joined: Thu Jul 12, 2007 4:50 am UTC
Location: Redmond, Washington

Re: dynamically size multidimensional arrays in C/C++

Postby Sc4Freak » Sat Feb 27, 2010 9:23 am UTC

Disclaimer: I'm a horrible, horrible pedant.

webb.am wrote:Now, to me, it seems like common sense that you should be able to do:

Code: Select all

const int a=10;
const int b=20;
int* exampleArray = new int[a][a];
.
.
.
delete exampleArray;
exampleArray = new int[b][b];

Dynamically allocated arrays in C++ do not store length data (although statically allocated arrays kind of do). This is because arrays are not first-class citizens - you receive a pointer from operator new[], not an array. Because pointers do not store length information, neither do dynamically-allocated arrays. And, of course, to index into a multi-dimensional array, you must know the length of all dimensions except one.

I can only think of one way around this:

Code: Select all

const int a=10;
int** exampleArray = new int*[a];
for(int i=0; i<a; i++)
    exampleArray[i] = new int[a];

I don't like this solution. The array is messy to create, messy to resize and messy to remove. It's horrible for higher dimensions.

If you want to be pedantic, that's not an array. An array (in the C definition) is required to be stored contiguously in memory. What you have there is an array of pointers, with each element pointing to an array of integers.

Does anyone have a neater solution? (I know 2D vectors can be easier to work with, but they're not always ideal)

Boost.MultiArray. If you're using C++, this is a solved problem already.

headprogrammingczar wrote:In C++, you can use a Vector<Vector*>, or however deep you want it. Just be sure to use indexes to access data, rather than pointers, since iirc, it uses realloc to increase in size.

std::vector resizes when you call functions like insert, resize, or push_back. Merely accessing the data (whether by index or pointer arithmetic) doesn't resize the vector. And the actual underlying method of memory allocation for a vector is determined by the allocator used. Further, I don't think the standard specifies the exact implementation details of the default allocator, only that it needs to be thread-safe.

cogman wrote:Consider this, at the low level, all arrays are basically 1d, the difference is in how they are interpreted. If you would like a n x n x n x n dynamic array, then you could just do something to the effect of

int**** 4darray = (int****)(new int[n * n * n * n]);

That will create an n x n x n x n array that you could access normally as 4darray[1][2][3][4].

No it won't. Your call to new[] returns an int*, which you are then casting to an int****. This is unsafe, and doesn't do what you think it does. Pointers are not arrays. Dereferencing (or indexing into) your 4darray variable will yield an int***, when the actual underlying type is int. Meaning that your int*** is invalid and points to garbage. Dereferencing it is undefined behaviour will very likely give you a segfault.

Xeio wrote:Also, here. Boost is your friend, seriously.

We have a winner!

User avatar
jaap
Posts: 2094
Joined: Fri Jul 06, 2007 7:06 am UTC
Contact:

Re: dynamically size multidimensional arrays in C/C++

Postby jaap » Sat Feb 27, 2010 9:51 am UTC

Sc4Freak wrote:
headprogrammingczar wrote:In C++, you can use a Vector<Vector*>, or however deep you want it. Just be sure to use indexes to access data, rather than pointers, since iirc, it uses realloc to increase in size.

std::vector resizes when you call functions like insert, resize, or push_back. Merely accessing the data (whether by index or pointer arithmetic) doesn't resize the vector.

I think headprogrammingczar merely meant that any pointers to the data are not guaranteed to remain valid if you do anything that could change the vector size as the data may be moved about in memory (by the equivalent of a realloc).

User avatar
Sc4Freak
Posts: 673
Joined: Thu Jul 12, 2007 4:50 am UTC
Location: Redmond, Washington

Re: dynamically size multidimensional arrays in C/C++

Postby Sc4Freak » Sat Feb 27, 2010 10:43 am UTC

Ah, right. In retrospect that makes a lot more sense. :P

User avatar
You, sir, name?
Posts: 6983
Joined: Sun Apr 22, 2007 10:07 am UTC
Location: Chako Paul City
Contact:

Re: dynamically size multidimensional arrays in C/C++

Postby You, sir, name? » Sat Feb 27, 2010 1:23 pm UTC

cogman wrote:Consider this, at the low level, all arrays are basically 1d, the difference is in how they are interpreted. If you would like a n x n x n x n dynamic array, then you could just do something to the effect of

int**** 4darray = (int****)(new int[n * n * n * n]);

That will create an n x n x n x n array that you could access normally as 4darray[1][2][3][4].

Enjoy.


Uh, that doesn't do what you think it does. In fact, it -couldn't- possibly, as you never tell the compiler the dimensions of the 4D array, and as such, it has no means with which to calculate the offset corresponding to the indices you feed it.
I edit my posts a lot and sometimes the words wrong order words appear in sentences get messed up.

MadRocketSci2
Posts: 69
Joined: Sat Nov 21, 2009 5:31 pm UTC

Re: dynamically size multidimensional arrays in C/C++

Postby MadRocketSci2 » Sun Feb 28, 2010 9:30 pm UTC

In C++, I always create a template class that, on constuction, allocates a 1D array of size [n*m], where element (n,m) corresponds to (m*n+n).

In the destructor, it frees the memory

In the resize method, I have it delete the underlying 1D array, then create a new 1D array of the new size (after various check proceedures), and point the pointer to the new 1D array, update all the length variables, ect.

Sets and gets retrieve elements of the 1d array.

Since it is a template class, you can derive classes for any object with a constructor, destructor, and copy constructor.

(edit) nevermind...
Last edited by MadRocketSci2 on Mon Mar 01, 2010 8:59 am UTC, edited 1 time in total.

User avatar
Sc4Freak
Posts: 673
Joined: Thu Jul 12, 2007 4:50 am UTC
Location: Redmond, Washington

Re: dynamically size multidimensional arrays in C/C++

Postby Sc4Freak » Mon Mar 01, 2010 4:35 am UTC

But for the 1D case, you've basically reimplemented std::vector, except your version is less generic, less safe, is much slower, and doesn't work with standard C++ algorithms. And for more than 1 dimension, you have the same thing except now you've reimplemented boost::multi_array.

Sorry if that was a bit blunt. But it's nothing personal - writing safe, generic, and performant containers is hard. That's why writing your own containers is rarely the best path to take - if it's a container that's not very specialised (like a simple dynamically-sized array), then the chances are that somebody else has already implemented it far better than you or I could alone.

If you're learning and want the experiencing of trying to write your own container, that's fine. For for production systems, there's no reason to roll your own when better pre-existing alternatives exist.

MadRocketSci2
Posts: 69
Joined: Sat Nov 21, 2009 5:31 pm UTC

Re: dynamically size multidimensional arrays in C/C++

Postby MadRocketSci2 » Mon Mar 01, 2010 8:47 am UTC

Well, I was also trying to learn about template classes that weekend.

I was going for something that behaved a bit more like MATLAB, where when you set an element that is outside of the current bounds of the array, the array resizes to include it, without the usual fuss. Either that, or it returns a flag that lets your program know it was out of bounds, rather than throwing an error and crashing.

cogman
Posts: 112
Joined: Sun May 18, 2008 2:17 pm UTC

Re: dynamically size multidimensional arrays in C/C++

Postby cogman » Mon Mar 01, 2010 2:38 pm UTC

You, sir, name? wrote:
cogman wrote:Consider this, at the low level, all arrays are basically 1d, the difference is in how they are interpreted. If you would like a n x n x n x n dynamic array, then you could just do something to the effect of

int**** 4darray = (int****)(new int[n * n * n * n]);

That will create an n x n x n x n array that you could access normally as 4darray[1][2][3][4].

Enjoy.


Uh, that doesn't do what you think it does. In fact, it -couldn't- possibly, as you never tell the compiler the dimensions of the 4D array, and as such, it has no means with which to calculate the offset corresponding to the indices you feed it.

ahh shoot, your right. You can do the opposite (4d -> 1d array) as what I said about the structure is true, but going the other way around isn't possible. Don't know why I thought it was.


Return to “Coding”

Who is online

Users browsing this forum: No registered users and 7 guests