Proper terminology for "dynamically allocated memory emulating multi-dimensional array"?

Question

Some time ago I asked a question in which I was told (in the commits) that using the term "multi-dimensional array" for a construct like this:

int **a;

Initialized like this:

a = malloc(n * sizeof(*a));
for (i = 0; i < n; ++ i)
    a[i] = malloc(m * sizeof(*a[i]));

is misleading and that this is "only an emulation of " a multi-dimensional array. Not being a native English speaker, I am having a hard time figuring out what is the proper terminology. Unfortunately, the guy who complained about the terminology was of no help himself.

Sure enough, the term "emulation of multi-dimensional array" is too long to be actually used in text/conversation.

To sum up:

What is the proper terminology for the construct above (specifically in C, if that makes a difference)?

Side question:

Is this terminology language agnostic? If not, how is it called in C++ for example?

Note: I'd be happy if your answer is linked with a reference.
Edit: I understand the difference between this construct and int a[n][m];. That's not the question.

Update

The memory allocated is not necessarily regular. This construction is more precise:

a = malloc(n * sizeof(*a));
for (i = 0; i < n; ++ i)
  if (needed[i])
    a[i] = malloc(m[i] * sizeof(*a[i]));
  else
    a[i] = NULL;

Side note (and besides the terminology): You do understand what the difference between that and a bidimensional array of size nxm is, right? — David Rodríguez - dribeas, Jul 20 '12 at 04:20

score 7 · Answer 1 · answered Jul 20 '12 at 04:18

7

I've always heard these referred to as "jagged arrays" -- even if each sub-array is the same length, they can be of different lengths, hence the term "jagged." (In a true multi-dimensional array, each dimension has a fixed size, and in this case only the first dimension is truly fixed.)

answered Jul 20 '12 at 04:18

cdhowie

158,093
24
286
300

I've always heard them called "ragged arrays" - I suspect one is a corruption of the other. – caf Jul 20 '12 at 05:02
I might be wrong, but I feel "jagged array" is a term made popular by the C# language as they had to distinguish between jagged arrays and true multi-dimensional arrays. – Jesse Good Jul 20 '12 at 05:07
@Jesse: Same distinction here, and in Java, and in most other languages that have a "true" multi-dimensional array type. – Ben Voigt Jul 20 '12 at 05:17
@BenVoigt: I don't want to get too pedantic, but AFAIK, C, C++ and Java do not have "true" multi-dimensional arrays, while C# does. Read the first line [here](http://www.eskimo.com/~scs/cclass/int/sx9.html) and this [SO question](http://stackoverflow.com/questions/5313832/multidimensional-arrays-in-java-and-c-sharp). – Jesse Good Jul 20 '12 at 05:39
@JesseGood: C++ is designed to provide good support for User Defined Types (including operator overloading), such that a multidimensional array class (see mention of boost's in my answer) can be as efficient as any inbuilt language feature could be. That's "true" for all intents and purposes. – Tony Delroy Jul 20 '12 at 10:02
1

@Jesse: `int a[6][7];` is a "true" multidimensional array in C and C++ (there's only one array, one block, all elements stored contiguously). Which is very different from the thing in this question. You cannot pass `int a[6][7];` to a function `f(int** a)`, they are not compatible. – Ben Voigt Jul 20 '12 at 12:27

score 1 · Accepted Answer · answered Jul 20 '12 at 04:35

1

It's an "array of (pointers to) arrays", the term is understood across a variety of languages, and applies whether the lengths of the element arrays are equal (square AoAs) or not (jagged AoAs).

answered Jul 20 '12 at 04:35

Ben Voigt

277,958
43
419
720

So in my original question (the one I linked), I'm supposed to say "I have an array of array of array of array of array of array"? Or "AoAoAoAoAoA"? – Shahbaz Jul 20 '12 at 04:45
I'll probably accept your answer, but what do you think of this term: "A dynamic 6-dimensional array"? That is, adding dynamic to make people understand it's `malloc`ed. – Shahbaz Jul 31 '12 at 09:04
@Shahbaz: You can certainly qualify your example with *dynamic*, as in "a dynamic array of arrays". But dynamic by itself is neither necessary nor sufficient to indicate this kind of array. – Ben Voigt Jul 31 '12 at 13:01

score 1 · Answer 3 · answered Jul 20 '12 at 05:42

"Nested arrays", or "arrays of arrays [of ...]".

While I don't think it supports differing dimensions, Boost has an offering in this vague space - http://www.boost.org/libs/multi_array/doc/user.html - the design decisions and interface may be worth consideration even if you're implementing something new.

score 0 · Answer 4 · answered Jul 20 '12 at 04:55

I would call the construct a "simulated multi-dimensional array" as they do in the c-faq. If you think that term is too long, you could say "simulated 2d array", etc. However, referring to int **a; as a multi-dimensional array should never be done, as it's type is a pointer to pointer to int. I think the distinction is that pointers can be used to construct arrays, but they will always remain as pointers. Also, it should be known that an array of pointers (int *a[10];) can also be used to construct jagged arrays, so the terminology would not be specifically referring to what you have.

Proper terminology for "dynamically allocated memory emulating multi-dimensional array"?

Update

4 Answers4