20

A simple question about the C programming language (ANSI-C):

Are the multi-dimensional arrays in C jagged?

I mean - are we talking about "array of arrays" (one array of pointers to other addresses in the memory) , or this is just "long one-dimensional array" (which is stored sequentially in the memory)?

What that bothers me is that I'm kinda sure that:

matrix[i][j] is equivalent to * ( * (matrix + i) + j)

Zero Piraeus
  • 56,143
  • 27
  • 150
  • 160
Programmer
  • 750
  • 2
  • 9
  • 17

6 Answers6

13

A multidimensional array in C is contiguous. The following:

int m[4][5];

consists of 4 int[5]s laid out next to each other in memory.

An array of pointers:

int *m[4];

is jagged. Each pointer can point to (the first element of) a separate array of a different length.

m[i][j] is equivalent to *(*(m+i)+j). See the C11 standard, section 6.5.2.1:

The definition of the subscript operator [] is that E1[E2] is identical to (*((E1)+(E2)))

Thus, m[i][j] is equivalent to (*(m+i))[j], which is equivalent to *(*(m+i)+j).

This equivalence exists because in most contexts, expressions of array type decay to pointers to their first element (C11 standard, 6.3.2.1). m[i][j] is interpreted as the following:

  • m is an array of arrays, so it decays to a pointer to m[0], the first subarray.
  • m+i is a pointer to the ith subarray of m.
  • m[i] is equivalent to *(m+i), dereferencing a pointer to the ith subarray of m. Since this is an expression of array type, it decays to a pointer to m[i][0].
  • m[i][j] is equivalent to *(*(m+i)+j), dereferencing a pointer to the jth element of the ith subarray of m.

Note that pointers to arrays are different from pointers to their first element. m+i is a pointer to an array; it is not an expression of array type, and it does not decay, whether to a pointer to a pointer or to any other type.

user2357112
  • 260,549
  • 28
  • 431
  • 505
  • `m+i` *is* an expression of a pointer-type. The type in this case is `int (*)[N]`, where N is the declare width of the inferior dimension. And a function parameter should be declared as a pointer to such a type accordingly if `m + i` is passed, just as if `m` is passed. (or punt and just declare `int param[][N]`, they're equivalent). – WhozCraig Feb 07 '14 at 10:49
  • 1
    @WhozCraig: `int (*)[N]` is a pointer to an array of ints, not an array itself. – user2357112 Feb 07 '14 at 10:51
  • Ok, I read that last paragraph a half dozen times, and it finally came out right in my head, sry for the extraneous post, you got it right. It was the "does not decay" (a word I absolutely detest on that note, as does the standard) that threw me. +1 btw – WhozCraig Feb 07 '14 at 10:52
  • @WhozCraig: Yeah, I don't think the standard ever uses the term. 6.3.2.1 part 3 says "an expression that has type ‘‘array of *type*’’ is converted to an expression with type ‘‘pointer to *type*’’", but "decay" is easier to Google. – user2357112 Feb 07 '14 at 11:00
  • 1
    I asked the question a long time on on SO where the term came from. The oldest reference anyone could find was to 1987. I just hate the term because it infers a functional action taken at runtime, and no such action exists. When discussing the differences, I often simply say, "pointers are variables that *hold* addresses (and have a separate distinct address of their own); arrays are variables that *are* addresses (and their "value" is said-address when assigned to a pointer =P). – WhozCraig Feb 07 '14 at 11:07
3

A consecutive memory area:

int arr[N][M];

A non-consecutive memory area:

int** arr = malloc(N*sizeof(int*));
for (int i=0; i<N; i++)
    arr[i] = malloc(M*sizeof(int));

You can use arr as a 2-dimensional array (e.g., arr[1][2] = 3) in both cases. But you can safely apply larger copy operations, such as memset(arr,0,N*M*sizeof(int)), only in the first case.

barak manos
  • 29,648
  • 10
  • 62
  • 114
  • Am I wrong thinking that matrix[i][j] is equivalent to *(*(matrix + i) + j)? – Programmer Feb 07 '14 at 10:26
  • Yes. You can use `matrix[i][j]` in both cases, but you can use `*(*(matrix + i) + j)` only in the second case. If you attempt to use it for a statically declared array (`matrix[N][M]`), then you will most likely perform an illegal memory access "in the outer `*`". – barak manos Feb 07 '14 at 10:28
  • @Elias Van Ootegem, isn't that exactly what I said in the comment??? OP asked "Am I wrong". I answered "Yes" and provided an example. – barak manos Feb 07 '14 at 10:33
  • 4
    You can use `*(*matrix+i)+j)` in both cases; it is exactly equivalent to `matrix[i][j]` by the definition of the indexing operator. – user2357112 Feb 07 '14 at 10:36
  • @barakmanos: rofl... just went on the _yes_ and _"the same?"_, and noticed I answered the OP's question in the same way: _"Am I wrong...?"_ > Yes – Elias Van Ootegem Feb 07 '14 at 10:37
  • @Elias Van Ootegem: 1. What does "rofl" mean? 2. I'm having second thoughts on this answer to begin with... – barak manos Feb 07 '14 at 10:39
  • @Programmer, I apologize for confusing you. Yes, they are equivalent statements. However, as explained in the answer, the memory-maps of a statically-allocated array and a dynamically-allocated array are different. – barak manos Feb 07 '14 at 10:45
  • @barakmanos: Rolling On the Floor Laughing -> I found it amusing that I misread your answer, whereas I said the same thing. and what is the part of your answer you're not sure about – Elias Van Ootegem Feb 07 '14 at 10:45
  • @Elias Van Ootegem: explained one comment above (and also stated by user2357112 four comments above). It's not within the answer itself, however, just on the comment-thread. – barak manos Feb 07 '14 at 10:46
  • @barakmanos Thanks, so - if in memory this is just "long one dimensional array", why *(*(matrix + i) + j) works correctly? This is contrasted to the way the array is organized in memory, isn't it? – Programmer Feb 07 '14 at 10:46
  • Whoops, missed a parenthesis. `*(*(matrix+i)+j)`, not `*(*matrix+i)+j)`. – user2357112 Feb 07 '14 at 10:46
  • @Programmer: That's just pointer arithmetic. If I have a string, say, "foobar", and set a pointer `p1` to point to `f`, and `p2` to `b`, then `*(p1+3)` or even `p1[3]` be the same as `p2[0]` or `*p2` – Elias Van Ootegem Feb 07 '14 at 10:50
  • @Programmer: The compiler still knows to address the "long one dimensional array" as a 2-dimensional array, because it is explicitly specified in the code. So `*(matrix+i)` is compiled into a pointer to the beginning of the `ith` row in the matrix, and `*(row+j)` is compiled into the value of the `jth` item in the row. – barak manos Feb 07 '14 at 10:52
  • There's no `new` in C, that's a bit odd. – unwind Feb 07 '14 at 10:57
  • @unwind: True, thanks for pointing that out (since the question is tagged under `c`); changed to `malloc` – barak manos Feb 07 '14 at 11:02
  • @barakmanos So, the array isn't jagged in memory, but in the code I should treat it as if it was jagged (hope you get my intention)? – Programmer Feb 07 '14 at 11:03
  • @barakmanos You seem to have C++ reflexes going strong. [Please don't cast the return value of `malloc()` in C](http://stackoverflow.com/a/605858/28169). :) – unwind Feb 07 '14 at 11:07
  • @Programmer: not sure what you mean by "jagged". If you mean "non-consecutively allocated", then yes - you can refer to any given element with simple indexing (`matrix[i][j]`), but you cannot perform larger read or write operations (such as `memcpy`, `memset` and `memcmp`), which are based on the assumption that the array occupies a consecutive fragment of memory. – barak manos Feb 07 '14 at 11:07
  • @unwind: Thanks for the advice (interesting post). – barak manos Feb 07 '14 at 11:09
2

This would depend.

Multidimensional arrays in C are sequentially arranged.

You can create jagged arrays if you want using pointers.

Aniket Inge
  • 25,375
  • 5
  • 50
  • 78
  • Thanks, I'll copy what I've written to Klas Lindback too: So, why matrix[i][j] is equivalent to *(*(matrix + i) + j), if we are talking about one dimensional array? This is confusing. – Programmer Feb 07 '14 at 10:17
  • That's not equivalent @Programmer. That means whatever is at an address pointed by whatever is pointed by `matrix + i` plus `j`. This would assume `matrix+i+j` contain a pointer. Which might give you a sigsegv – Aniket Inge Feb 07 '14 at 10:20
  • equivalent would be `*(matrix +i + j)` – Aniket Inge Feb 07 '14 at 10:21
  • Thanks, but this isn't what my output shows. Try to run the following program, please, and look at the output (my output is "wrong"): #include int main(void) { int i, j; int matrix[3][2] = { {1, 2}, {3, 4}, {5 , 6} }; for (i = 0; i < 3; ++i) for (j = 0; j < 2; ++j) printf("%d ", *(matrix + i + j)); getchar(); return 0; } – Programmer Feb 07 '14 at 10:23
  • So I'm probably confused. Isn't it a multi-dimensional-array? And if so, why is it jaggged if I didn't use pointers like you have said? – Programmer Feb 07 '14 at 10:30
  • let us [continue this discussion in chat](http://chat.stackoverflow.com/rooms/47004/discussion-between-aniket-and-programmer) – Aniket Inge Feb 07 '14 at 10:30
1

If you declare a multi-dimensional array, you get "long one-dimensional array" (which is stored sequentially in the memory).

If you declare a pointer to pointer (to pointer....) you get arrays of arrays.

This difference is a source of much confusion for beginner C programmers.

Klas Lindbäck
  • 33,105
  • 5
  • 57
  • 82
  • Thanks. So, why matrix[i][j] is equivalent to *(*(matrix + i) + j), if we are talking about one dimensional array? This is confusing. – Programmer Feb 07 '14 at 10:16
  • @Programmer It is not. It should even give you an error at compile-time. `*(matrix + i + j * dim_1)` would be equivalent to `matrix[i][j]` where *dim_1* is the number of elements for the major component. – Niklas R Feb 07 '14 at 10:25
  • um. no, those aren't even close to the same. Firstly, `*(matrix + i + j * dim_1)` would result in a `int(*)[N]` positioned at `matrix[i+j*dim_1]`, completely different than the OP's expression. Secondly, if this *was* done purposely as a single linear 1-dim, the indexing would be *(ar + i*dim_0 + j) to equate to the correct position of what would be `mat[i][j]` in a 2D declared matrix of `int mat[dim_1][dim_0];` (which is, I think, what you were trying to express). – WhozCraig Feb 07 '14 at 11:04
  • @Programmer The elements of matrix[i][j] are stored sequentially, like a one-dimensional array is, but conceptually it is 2-dimensional. `matrix[i][j]` is adjacent to `matrix[i][j+1]` while `matrix[i][j]` is located dim_1 `int`s away from `matrix[i+1][j]`. – Klas Lindbäck Feb 07 '14 at 11:06
0

An array or arrays, such as int matrix[A][B] is not jagged, as each element of matrix is an array of B int.

You want to know that the outcome of *(*(matrix+i)+j) is and compare it to the outcome of matrix[i][j].

Since the type of matrix is array of A array of B int, then the expression matrix+i is a pointer that points to the ith array of B int of matrix, and its type is int (*)[B]. Dereferencing this expression results in an array of B int. The expression *(matrix+i)+j) results in a pointer to the jth int of that array. Dereferencing that expression results in an int. This is equivalent to what the expression matrix[i][j] would do.

An array of pointers, such as int *matrix[A], may be jagged, as each element of matrix may point to a different sized allocation.

jxh
  • 69,070
  • 8
  • 110
  • 193
  • Am I wrong thinking that matrix[i][j] is equivalent to *(*(matrix + i) + j)? – Programmer Feb 07 '14 at 10:26
  • No, but the type of `matrix` matters in terms of figuring out what the additions actually do. – jxh Feb 07 '14 at 10:35
  • If matrix is declerated like this: int matrix[2][3]; Is it wrong to say that matrix[1][2] is like writing *(*(matrix + 1) + 2)? – Programmer Feb 07 '14 at 10:38
0

You are right, that matrix[i][j] is equivalent to *(*(matrix + i) + j), since arr[i] is equivalent to *(arr + i). However, please keep in mind, that if arr is declared as

int arr[64];

then any reference to arr may be implicitly converted to &arr[0], that is a pointer to the first element. Same thing happens with arrays of arrays:

int matrix[8][8];

Here matrix has type int[8][8], which is automatically converted to int (*)[8] when you add an integer to it, as in matrix + i. Then *(matrix + i) has type int[8], which is again converted to int * when you add j, so *(matrix + i) + j has type int *, therefore *(*(matrix + i) + j) has type int as expected.

So the point is, that arrays are not pointers, it is just that they can be implicitly casted to a pointer to their first element.

So if you allocate arrays of arrays like above (int matrix[8][8];), then then all elements are consecutive in memory.