How is a dynamic 2D array stored in memory?

Question

How is a 2D array stored in memory?

I thought of the following approach where strings are stored as solid blocks of memory.

| _________ || _________ | ________ | ________ | ... | _________ |

Elements are attached as (i, j) → n * i + j, where n is the dimension of the matrix (if it is equal to nxn).

But what if I want to add a new column to it? I have to update every (n + 1) th element in each row, and also shift them to the right, but this is too expensive a calculation.

Another option is to copy the matrix to a new location and update the rows with the new column elements on the fly. But this is not too efficient if the array is large.

And finally, the third option that I thought was to allocate a fixed amount of memory for each row, and when I add a new column, I do not need to translate the rows to the right.

I cannot have spaces in memory, so all blocks must be contiguous.

I do not ask for the implementation of C using pointers and real RAM memory, I'm just interested in learning about a theoretical approach to storing a dynamic 2d array in memory, since it is easy to add new rows or columns to it.

Are there other more effective approaches?

Answer 1

If you know that you are creating a 2D array that you expand, one approach would be to select a larger size than you need in each dimension. Keep track of the actual size and the distributed size, and when the actual size exceeds the allocated size, do the following:

• double selection size
• copy all data from the old array to the new
• free the old array

This will be a two-dimensional extension of the general methodology for the distribution of 1D dynamic arrays.

Answer 2

If you need arrays for expansion and continuity in memory, one way to achieve this is to simply use the 1st array and "fake" the second dimension.

If your initial 1d array has more space than all of your 2d arrays, it won’t need to move in memory (potentially avoiding spaces). However, depending on how you implement it, an insert that enlarges one of the subcells may need to drag later elements (you may also have spaces in your array, but I believe this violates your requirements without spaces).

If you really need 2 dimensions then greg's answer is the way to go. If you know the size of your data to begin with, this will greatly simplify.