How is a dynamic 2D array stored in memory?

Question

How is a 2D array stored in memory?

I thought about the following approach, where rows are stored as contigous blocks of memory.

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

The elements are accesed like (i,j) -> n*i+j, where n is the dimension of the matrix (supposing it is nxn).

But what if i want to add a new column to it? I'd have to update each (n+1)th element in each row and also shift them to right, but that's too computationally expensive.

Another option would be to copy the matrix in a new location and update the rows with the new column's elements on the fly. But that's not too efficient too if the array is big.

And finally the third option i thought of is to allocate a fixed amount of memory for each row and when i add a new column i don't have to shift the rows to right.

I can't have gaps in the memory, so all blocks must be contigous.

I'm not asking for a C implementation using pointers and the actual RAM memory, i'm just curious about a theoretical approach of storing a dynamic 2d array in memory so as it is easy to append new rows or columns to it.

Are there other more efficient approaches?

Answer 1

If you know you're creating a 2D array that you will expand, one approach would be to allocate more size than you need in each dimension. Keep track of the actual size and the allocated size, and when the actual size exceeds what is allocated, do the following:

• double the size of the allocation
• copy all the data from the old array to the new one
• free the old array

This would be a 2D extension of a common technique for allocating dynamic 1D arrays.

Answer 2

If you need the arrays to expand and be contiguous in memory, one way to achieve this is to simply use a 1d array and 'fake' the 2nd dimension.

If your initial 1d array has more space than all your 2d arrays requires, it wouldnt require moving in memory (potentially avoiding gaps). However depending on how you implement it, an insert that makes one of the sub arrays grow may requires shuffling later elements down (you could also have gaps in your array, but I believe this violates your no gaps requirement).

If you actually do need 2 dimensions, then greg's answer is the way to go. If you know the size of your data to begin with, it makes it much easier.