NOTE:
These are a little sketchy...I'll fill in details 'soon'.
There are two basic ways to approach the creation of 2D arrays on the heap: tedious and annoying. That's not to say you shouldn't do so, just that you need to examine each to decide which is best for you/your application.
This approach is the most 'obvious'. It uses an array of pointers where each element points to an array of data:
arr1
+---+
| , |
+-|-+ +---+---+---+---+
| +->| | | | |
| | +---+---+---+---+
| |
| | +---+---+---+---+
| | +-->| | | | |
\ / | | +---+---+---+---+
, | |
+---+ | | +---+---+---+---+
| , |-+ | +->| | | | |
+---+ | | +---+---+---+---+
| , |---+ |
+---+ |
| , |------+
+---+ +---+---+---+---+
| , |---------->| | | | |
+---+ +---+---+---+---+
| , |--+
+---+ | +---+---+---+---+
+->| | | | |
+---+---+---+---+
In code terms, we'd have:
type **arr1 = nullptr;
arr1 = new(nothrow) type* [ROWS];
if (arr1 != nullptr)
{
r = 0;
arr1[r] = new(nothrow) type [COLS];
while (arr[r] != nullptr // we succeeded in last allocation
&& r+1 < ROWS) // and there is room for the ~next~ allocation
{
arr1[++r] = new(nothrow) type [COLS]; // allocate into the next spot
}
num_rows = r+1; // adjust for 0-start
}
else
{
num_rows = 0; // we got no space at all!
}
Note how the allocation stops when a row fails to allocate or when we've allocated all the rows. But we keep track of how many rows were successfully allocated for later with the num_rows helper variable.
Once allocated, we can use this array normally:
for (r = 0; r < num_rows; r++)
{
for (c = 0; c < COLS; c++)
{
// use arr1[r][c] like normal
}
}
But, care must be taken when we're done to avoid leaving allocated but inaccessible fragments of memory:
for (r = 0; r < num_rows; r++) // delete each row
{
delete [] arr1[r];
arr1[r] = nullptr;
}
delete [] arr1; // then delete the outer array
arr1 = nullptr;
The other way, less obvious to the novice, but less 2D friendly, is to map 2D coordinates into a 1D array. The standard formula is:
arr2D[r][c] == arr1D[r*COLS+c]
This is how statically allocated 2D arrays are actually stored, BTW. Instead of our traditional idea of:
C O L S
0 1 2 3
+----+----+----+----+
0| | | | |
R +----+----+----+----+
1| | | | |
O +----+----+----+----+
2| | | | |
W +----+----+----+----+
3| | | | |
S +----+----+----+----+
4| | | | |
+----+----+----+----+
A 2D array is actually stored like so:
R O W S
C O L S C O L S C O L S C O L S C O L S
+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+
| | | | | | | | | | | | | | | | | | | | |
+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+
0,0 0,1 0,2 0,3 1,0 1,1 1,2 1,3 2,0 2,1 2,2 2,3 3,0 3,1 3,2 3,3 4,0 4,1 4,2 4,3
Notice how, for instance, the first element of the second row ([1][0]) is the fifth element of the linearized (1D) diagram: 1*COLS+0. And similarly for the third element of the fifth row ([4][2]): 4*COLS+2.
(Isn't it cool how this scheme takes into account that each row is COLS elements long and takes advantage of our 0-based indices?)
With this approach, you can allocate your array in one fell swoop:
type * arr2 = nullptr;
arr2 = new(nothrow) type [ROWS*COLS];
(Note that there is no chance to have lost desired rows — we get the whole array or nothing.)
And use it:
for (r = 0; r < ROWS; r++)
{
for (c = 0; c < COLS; c++)
{
// use arr2[r*COLS+c]
}
}
And the deallocation is simple, too:
delete [] arr2;
arr2 = nullptr;
The annoying thing is the need to map the coordinates during use. Some folks try to mask it with a concoction such as:
inline type & map2D(type * arr, size_t row, size_t col, size_t COLS)
{
return arr[row*COLS+col];
}
But this is just a bit icky — it still doesn't hide enough details. If you are going to use this approach, the coolest way would have to be to embed the array in a class and overload operator() to do your 2D indexing:
class Arr2D
{
type * arr2;
size_t ROWS, COLS;
void alloc(void) { arr2 = new(nothrow) type [ROWS*COLS]; return; }
public:
Arr2D(void) : arr2(nullptr), ROWS(0), COLS(0) { }
Arr2D(size_t R, size_t C) : arr2(nullptr), ROWS(R), COLS(C) { alloc(); }
// copy constructor left to reader!!!
// operator= left to reader!!!
~Arr2D(void) { delete [] arr2; }
type & operator() (size_t r, size_t c) { return arr2[r*COLS+c]; }
// *ALL* error checking left to reader!!!
};
Now you can do something like this:
Arr2D ar(ROWS,COLS);
for (r = 0; r < ROWS; r++)
{
for (c = 0; c < COLS; c++)
{
// use ar(r,c)
}
}
Still not completely normal, but you've hidden the allocation details, the deallocation details, and, of course, the mapping details inside the class.
Another possibility would be to use a helper position class
The tedious method can also be hidden in a class using operator(), but this loses your natural use of [][] for indexing in 2D.
The tedious method can support 'ragged' arrays: those whose rows are not all the same length. In some applications this can be important.
The annoying method might seem slower because you have to multiply and add to reach the correct address, but consider that a normal (statically declared) 2D array does the exact same thing. Only the compiler does the multiply and add for you. (Also, there are methods to speed up these calculations by caching the current pointer and simply retrieving the next element.)
The tedious method might seem faster because it uses our normal [][] notation for access, but consider that it no longer is normal and that you are really doing two dereference operations. Unless the whole array is in the processor's cache, this could take quite a while to follow pointers to arbitrary places in RAM.
Both methods can be easily extended to multiple dimensions. The tedious way naturally extends as you'd expect (add a *, add another loop for allocation, etc.). The annoying way's mapping formula for 3D is: arr[p*ROWS*COLS+r*COLS+c]. Here p is the plane or cross-section of the 3D you want. I'll let you continue the math to multiple dimensions. (Note that you can factor out the multiply by COLS from the first two terms to speed things up a bit. This is known as Horner's method.) (Also note that you can make this pattern formulaic and use a 'dimensional' array to store the offsets for faster access.)
But, for those out for the ultimate best of both worlds (and willing to pay the costs of both worlds), try out this variation. In addition to the 1D mapping, we make an array of pointers to the beginning of each row within the linearized space:
0,0 0,1 0,2 0,3 1,0 1,1 1,2 1,3 2,0 2,1 2,2 2,3 3,0 3,1 3,2 3,3 4,0 4,1 4,2 4,3
+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+
| | | | | | | | | | | | | | | | | | | | |
+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+
' ' ' ' '
/ \ / \ / \ / \ / \
+---+ | | | | |
| , |-----+ | | | |
+---+ | | | |
| , |-------------------------+ | | |
+---+ | | |
| , |---------------------------------------------+ | |
+---+ | |
| , |-----------------------------------------------------------------+ |
+---+ |
| , |-------------------------------------------------------------------------------------+
+---+
In code this might look something like this:
// declaration
type * data = nullptr, ** arr2D = nullptr;
// allocation
data = new(nothrow) type [ROWS*COLS]; // allocate linearized space
if (data != nullptr)
{
arr2D = new(nothrow) type* [ROWS]; // allocate row pointers
}
if (arr2D != nullptr)
{
for (size_t r = 0; r != ROWS; r++) // aim row pointers
{
arr2D[r] = data + r*COLS;
}
// access (in a pair of for loops)
arr2D[r][c]
}
// deallocation
delete [] arr2D;
delete [] data;
Although we have the potential of failing to allocate the row-start pointers array separately from the data's allocation, this method can give nicer access patterns for general use. (You can even place a conditional in your class' accessor function to take advantage of the [][] when arr2D allocated or perform the mapping calculation when it failed. *bounce*)