2

I always believed that in C :

int a[5][3]={1,2,3,4,5,6,7,8,9,10,11,12,13,14,15};

refers to an array of arrays and in memory fifteen contiguous blocks are stored but a[0] is the pointer to a[0][0] and a[1] is the pointer to a[1][0] and so on. So I thought it to be similar to be an array of pointers. What is the difference between them?

user1369975
  • 430
  • 1
  • 6
  • 19

3 Answers3

3

Arrays and pointers have a very curious and intimate relationship in C (and C++). In most contexts, if you have something that is an 'array of X', then it will be silently converted to a 'pointer to X' that points at the first element of the array.

Your belief that

int a[5][3];

creates an array of arrays is entirely correct. According to the declaration, it is an array of 5 arrays of 3 ints and it occupies 15 contiguous integers in memory.

Where you go wrong is in believing a[0] to be a pointer. In fact, a[0] is the first sub-array of a and is itself an array of 3 ints. However, due to the curious relationship between pointers and arrays, the expression a[0] is almost always converted to a pointer.

One of the major differences between an array of arrays and an array of pointers is in where the array elements reside. An array of arrays will always occupy a contiguous block of memory, but the pointers in an array of pointers will each refer to their own (often disjoint) blocks of memory.

Bart van Ingen Schenau
  • 15,488
  • 4
  • 32
  • 41
  • If you would add a note " and it occupies 15 contiguous integers in memory" to say "in the C implementation" would help. – Jimmy Hoffa Jul 23 '13 at 15:16
  • 1
    Also an array of pointers (to arrays) could also describe a jagged array, as opposed to a 2d array as user1369975 is describing it. – TimG Jul 23 '13 at 16:35
  • @JimmyHoffa: In what way would that addition help? – Bart van Ingen Schenau Jul 23 '13 at 16:38
  • @BartvanIngenSchenau in many languages saying an array occupies contiguous space in memory is inaccurate, you're speaking about C so it's accurate here but if you would just qualify that statement as being about C it would make sure no poor green Ruby or PHP developer in the future misconstrues your statement – Jimmy Hoffa Jul 23 '13 at 16:43
  • @JimmyHoffa: The question is clearly tagged as a C question (and arguably belongs on SO). If a PHP or Ruby developer gets an incorrect impression because they did not pay attention to the tags, I consider that to be their problem. As a side note, I nearly downvoted your answer, because arrays in C are definitely *not* a high-level construct. – Bart van Ingen Schenau Jul 23 '13 at 17:01
  • I didn't immediately see the C tag; and the tag is the only place C is even mentioned in the Q, other people will make the same mistake, so in the future people will make that misinterpretation of your answer as well. I'll remove my answer because it doesn't apply since this question is *only* about C, but it would help future visitors if you made that fact clear in your answer, and it will harm them if you don't.. – Jimmy Hoffa Jul 23 '13 at 17:05
  • 1
    @JimmyHoffa: I have edited the question instead, to make it more obviously about C. – Bart van Ingen Schenau Jul 23 '13 at 17:15
  • I'm still combing the answer and comments to find out what made my answer so horribly wrong as to be deserving of -5. TimG even says that an array **of pointers** could be a jagged array. – Katana314 Jul 23 '13 at 17:49
0

Arrays and pointers loosely equate to the same thing. When you declare an array N long, you're allocating a block of memory N long (times the size of the value type) and returning the pointer to the first element. Expressions like arr[2] then retrieve a value from that memory by counting forward from that first pointer. If you have an array of arrays, then all you're storing in the first one (in your a array) is pointers to where the other arrays are stored. (That said, I believe they should be in a contiguous block as you said)

Does that help the explanation somewhat?

Katana314
  • 8,429
  • 2
  • 28
  • 36
  • 1
    No pointers != arrays. Arrays aren't first class and decay to pointers when used in expressions. This difference is exposed with extren declarations and `sizeof` – daniel gratzer Jul 23 '13 at 14:22
  • Join [The Whiteboard](http://chat.stackexchange.com/rooms/21/the-whiteboard) chat if you want to understand what happened with your answer – Jimmy Hoffa Jul 23 '13 at 17:58
  • @Katana314: The downvotes you got over at P.SE were most likely triggered by your first sentence. Equating pointers to arrays is one of the hardest misconceptions in C to get rid of. If you think of pointers and arrays as the same, then you *will* be bitten by hard to understand errors. – Bart van Ingen Schenau Jul 25 '13 at 11:30
0
 int a[5][3]={1,2,3,4,5,6,7,8,9,10,11,12,13,14,15};

This is a true two dimensional array: 15 int sized locations have been set aside and the conventional rectangular subscript is used to find the element a[row][col]

int *b[5];

This is an array of pointers which allocate 5 pointers and is not initialized but a[3][2] and b[3][2] are both syntactically legal references to a single int.

Assuming that each element of b does point to a three-element array, then there will be 15 ints set aside, plus five cells for the pointers.

The important advantage of the pointer array is that the rows of the array may be of different lengths. That is, each element of b need not point to a three-element vector, some may point to two elements, some to nine, and some to none at all.