StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p>This is something that comes up a lot, so I will attempt to explain it as clearly as I can.</p> <p>When you make an array, it stores the elements contiguously in memory, so:</p> <pre><code>int arr[2] = { 1, 2 }; </code></pre> <p>Translates to:</p> <pre><code>arr: +---+---+ | 1 | 2 | +---+---+ </code></pre> <p>A pointer points to an object in memory, and when dereferenced, via unary <code>*</code> or via <code>[]</code>, it accesses that contiguous memory. So after</p> <pre><code>int *ptr = arr; </code></pre> <p><code>ptr</code> (or <code>&ptr[0]</code> if you like) points to the box <code>1</code> is in, and <code>ptr + 1</code> (or <code>&ptr[1]</code>) points to the box <code>2</code> is in. This makes sense.</p> <p>But if arrays are contiguous in memory, arrays of arrays are contiguous in memory. So:</p> <pre><code>int arr[2][2] = {{ 1, 2 }, { 3, 4 }}; </code></pre> <p>Looks in memory like this:</p> <pre><code>arr: +---+---+---+---+ | 1 | 2 | 3 | 4 | +---+---+---+---+ </code></pre> <p>Which looks a lot like our flat array.</p> <p>Now, let's consider how a pointer to a pointer to an <code>int</code> would be laid out in memory:</p> <pre><code>ptr: +-------+-------+ | &sub1 | &sub2 | +-------+-------+ sub1: +---+---+ | 1 | 2 | +---+---+ sub2: +---+---+ | 3 | 4 | +---+---+ </code></pre> <p><code>ptr</code> (or <code>&ptr[0]</code>) points to <code>sub1</code>, and <code>ptr + 1</code> (or <code>&ptr[1]</code>) points to <code>sub2</code>. <code>sub1</code> and <code>sub2</code> have no actual relation to each other, and can be anywhere in memory, but because it's a pointer <em>to a pointer</em>, the double-dereference of a 2D array is preserved, even though the memory structure is not compatible.</p> <p>Arrays of type <code>T</code> decay to pointers to type <code>T</code>, but arrays of arrays of type <code>T</code> do not decay to pointers to pointers to type <code>T</code>, they decay to pointers to arrays of type <code>T</code>. So when our 2D <code>arr</code> decays to a pointer, it is not a pointer to a pointer to an <code>int</code>, but a pointer to an <code>int [2]</code>. The full name of this type is <code>int (*)[2]</code>, and to make your line of code work you'd want to use</p> <pre><code>int (*ptr)[2] = arr; </code></pre> <p>Which is the correct type. <code>ptr</code> expects to point to a contiguous array of memory, like <code>arr</code> does - <code>ptr</code> (or <code>&ptr[0]</code>) points to <code>arr</code> and <code>ptr + 1</code> (or <code>&ptr[1]</code>) points to <code>&arr[1]</code>. <code>ptr[0]</code> points to the box that holds <code>1</code>, and <code>ptr[1]</code> points to the box that holds <code>3</code>, so <code>ptr[0][0]</code> yields 1, <code>ptr[0][1]</code> yields 2, and so on.</p> <p>Why do you need to know this? 2D pointers seem more complicated than they're worth - if you were using <code>malloc</code> you'd have to call <code>malloc</code> repeatedly in a loop, and do the same for <code>free</code>. OR, you could use some evil* trickery to make a flat, 1-dimensional allocation of memory <em>act</em> like a 2D array:</p> <pre><code>// x and y are the first and second dimensions of your array // so it would be declared T arr[x][y] if x and y were static int (*arr)[y] = malloc(x * y * sizeof(arr[0][0])); if(!arr) /* error */; </code></pre> <p>Now <code>arr</code> points to a contiguous block of arrays of size <code>y</code> of <code>int</code> objects. Since the object it points to is an array, we don't need the double-pointer-indirection of <code>int **</code> objects, and when you're done, you can free it with one call:</p> <pre><code>free(arr); </code></pre> <p>Compare this to a version using <code>int **</code>:</p> <pre><code>int **arr = malloc(x * sizeof(*arr)); if(!arr) /* error */; for(size_t ii = 0; ii < x; ii++) { arr[ii] = malloc(y * sizeof(**arr)); if(!arr[ii]) { free(arr[ii]); free(arr); } } // do work for(size_t ii = 0; ii < x; ii++) free(arr[ii]); free(arr); </code></pre> <p>The above code has a memory leak. See if you can find it. (Or just use the version with those seemingly tricky pointers-to-arrays.)</p>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload