AboutRalph McArdell Expertise I am a software developer with more than 10 years C++ experience and over 20 years experience developing a wide variety of applications for Windows
NT/2000/XP, UNIX, Linux and other platforms. I can help with basic to advanced C++, C, software development and many platform specific and system development problems.
Experience My career started in the mid 1980s working as a batch process operator for the now defunct Inner London Education Authority, working on Prime mini computers. I then moved into the role of Programmer / Analyst, also on the Primes, then into technical support and finally into the micro computing section, using a variety of 16 and 8 bit machines.
Following the demise of the ILEA I worked for a small company, now gone, called Hodos. I worked on a part task train simulator using C and the Intel DVI (Digital Video Interactive) - the hardware based predecessor to Indeo. Other projects included a CGI based train simulator (different goals to the first), and various other projects in C and Visual Basic (er, version 1 that is).
When Hodos went into receivership I went freelance and finally managed to start working in C++. I initially had contracts working on train simulators (surprise) and multimedia - I worked on many of the Dorling Kindersley CD-ROM titles and wrote the screensaver games for the Wallace and Gromit Cracking Animator CD.
My more recent contracts have been more traditionally IT based, working predominately in C++ on MS Windows NT, 2000. XP, Linux and UN*X. These projects have had wide ranging additional skill sets include system analysis and design, databases and SQL in various guises, C#, client server and remoting, cross porting applications between platforms and various client development processes.
On another avenue I have started writing software for Symbian based devices (mobile phones).
Expert: Ralph McArdell Date: 4/25/2008 Subject: deleting multidimensional array pointers
Question
hello
if i created a pointer to an array
i would go like this
int *array = new int[size];
and when deleting i would type this code
delete []array
how can i do the same for
multidimensional arrays of pointers??
thanks
Answer Your question is ambiguous. Do you mean an array of pointers used like a multi dimensional array or an actual multi dimensional array that contains pointers to single data items?
1/ Array of pointers used like a multi dimensional array
--------------------------------------------------------
This is similar to your previous question on deleting linked lists. You first delete all the pointed to items in the array then delete the array itself using delete [], for example:
#include <iostream>
int main()
{
int const n_rows(10);
int const n_columns(20);
// Allocate an array of n_rows pointers to int:
int * *p = new int * [ n_rows ];
// The row array pointers are initialised to rubbish. We
// have to allocate an array of column elements for each row:
for ( int r = 0; r < n_rows; ++r )
{
// Allocate the column array for this row:
p[r] = new int[n_columns];
// Write values to the elements
for ( int c = 0; c < n_columns; ++c )
{
p[r][c] = r*1000 + c;
}
}
// Display the values in the arrays:
for ( int r = 0; r < n_rows; ++r )
{
for ( int c = 0; c < n_columns; ++c )
{
std::cout << "p[" << r << "][" << c
<< "]=" << p[r][c]
<< " ";
}
std::cout << "\n";
}
// To clean up we must first delete the column arrays for
// each row...
for ( int r = 0; r < n_rows; ++r )
{
delete [] p[r];
}
// ... and then delete the row pointer array itself:
delete [] p;
return 0;
}
2/ Actual multi dimensional array that contains pointers:
---------------------------------------------------------
In a similar way to above, however you may need to use nested loops to access each element pointer and use delete (not delete []), unless elements again point to arrays.
We only ever have a choice of dynamically creating and deleting scalar (single) object with new and delete or an array using new [] and delete []. This is because in C and C++ built in arrays are really just a chunk of contiguous memory. The dimensionality is just about how the items within that block are identified. The [] on the new and delete operators just tells the compiler that there are many objects that need to be constructed or destructed rather than one. No matter how you slice it up the compiler _always_ knows how much you are asking for in all but one dimension (see below).
Starting with single dimensional arrays as an example. In a single dimensional array we identify an object in an array by a single positive integer index value. This calculates where in the block of memory assigned to the array the object starts at by multiplying the size of an object by the index. This offset is added to the address of the start of the array.
So if we have an array of char (which by definition has a size of 1) starting at address a the nth char in the array will be at address a + n*1 or just a + n. If we have an array of int of size 4 starting at address a1 then the location of the nth int in the array is given by a1 + n*4.
In fact in C and C++ the above is the underlying form of arrays. The name of an array on its own is equivalent to a pointer to the first element of the array - array on its own evaluates to the same as &array[0], where & here is the address-of operator.
The notation using the subscript operator as in array[i] is equivalent to *(array+i). In C and C++ adding a value to a pointer adds the value times the size of the object to which the pointer points. Thus if array is an array of char, size 1, then array + 1 adds one to the address of the initial element of the array. If array is an array of int of size 4 then array + 1 adds 1*4 to the address of the initial element of the array. The * operator in *(array + i) is the dereference operator - that is we want the item at the resultant address not the address itself.
OK so we have:
- array is equivalent to &array[0]
- pointer_to_t + n yields an address of pointer_to_t + n*(sizeof t) where t is some type
- array[i] is equivalent to *(array + i)
Now onto the next example: two dimensional arrays. For the moment I shall ignore dynamically creating 2D array and stick to basics.
We define a 2D array by using two sets of [] with dimension values when the array is declared (which is also a definition):
T array_row_col[10][20];
Just as in the single dimensional array case this allocates a single, contiguous, block to memory. In this case the number of elements is calculated by multiplying the two dimensions together: 10*20 = 200 elements. Each element stores a T, and thus is of size sizeof T, so the size of the memory allocated would be at least 10*20*(sizeof T). I say at least as the compiler may allocate more if it needs to - for example to align the next item on an n-byte boundary (or n-word boundary if the machine is word addressed) or to add padding between items to help debug builds check for array overrun accesses.
So that is how to declare the size of the dimensions of a 2D array, how about access to elements in a 2D array? Well we still need to come up with a single address from the supplied data. These data are the array's initial element address (&array[0][0]) and the row and column index values. As C/C++ takes into account the size of each element I shall ignore it as it will probably just get in the way <g>.
OK so the start address part is the same as for the 1D array case (other than requiring two index values). The problem then is reduced to calculating a single offset value from the row and column index values. This is done by using the geometry of the array - that is the dimension values. In fact only one of the dimensions is required. Let us draw out the array with each element having its 1D offset values shown at each position in the array. There are two obvious ways to do this: j columns of i elements or i rows of j elements (view with a fixed pitch font such as Courier):
20 columns of 10 elements
--------------------------
You will notice that in the first example each column starts with a multiple of the number of items in each column: 0, 10, 20 etc., thus the start of each column is the column number (0, 1,2 etc.) multiplied by the dimension of the rows in each column, as used in the declaration of the array:
T array_row_col[10][20];
Thus the offset for each element starting on a new column is 10*column_index. To get to a specific row within each column we just add the row index: 10*column_index + row_index.
The second example is similar except that the roles of row and column are reversed. Here each row starts on a multiple of the number of columns: 0, 20, 40 etc., thus the start of each row is the row number multiplied by the dimension of the columns in each row, as used in the declaration of the array.
Thus the offset for each element starting on a new row is 20*row_index. To get to a specific column within each row we just add the column index: 20*row_index + column_index.
So which one does C++ and C use? In fact they use the second form:
20*row_index + column_index
Or more generally:
Given an array:
T array[NumRows][NumCols];
The element array[row][col] is given by:
*(&array[0][0] + (NumCols*row + col))
or just:
*(array + (NumCols*row + col))
This approach can be expanded to greater dimensions if required, for example for a 3D array we get:
(Note: I tried to get the above correct and apologise if in fact I have made a mistake and got it wrong!)
Notice that the order of specification of x, y and z is reversed to the normal order. This is because for the 2D case the column dimension is equivalent to the x dimension and the row to the y, thus we have:
T array[NumRows][NumCols];
Would map to
T array[NY][NX];
More importantly note that the calculation of an element in a multi dimension array depends on all array dimensions except the first - the one nearest the name of the array, and the compiler needs to know these values at compile time (when you compile your code).
This is important because it has a knock on effect for specifying multi dimensional arrays dynamically. Only one dimension can vary at runtime - the first (left most) one because the compiler has to know the dimension values of all the other dimensions of the array so it can perform the many-indexes to single offset calculations shown above.
The other thing about specifying multi dimension arrays dynamically is the syntax for the type declaration is horrible! In effect for a dynamically allocated array of T of N dimensions we have to declare a pointer to an array of T of n-1 compile time constant sized dimensions. Thus if we wish to have a 2D array of int dynamically allocated what we actually allocate dynamically is a single dimensional array of a compile time constant sized single dimensional array of int (ummm, sorry about that but that's the way it works out - you might like to try reading that through a couple of times!).
To demonstrate dynamically creating a multi dimensional array dynamically I shall use a class that contains an int value called Element whose only purpose is to help us see what is happening - hence it is not meant to be an example of general good development practice!
The Element class has a default constructor that initialises its int member to a value given by a static member, which is incremented after each Element i member initialisation. Thus the first Element created has an i member value 0, the next 1, then 2 etc...
When an Element object is destroyed its destructor displays the value of its i member. The code for Element is as follows:
#include <iostream>
class Element
{
int i;
static int s_elementCount;
public:
Element() : i(s_elementCount++) {}
~Element() { std::cout << "Deleting Element #" << i << '\n'; }
};
int Element::s_elementCount(0);
This can be used to create a 2D array of Element objects dynamically with a compile time (constant) number of columns and a runtime defined (variable) number of rows. Here is an example:
#include <iostream>
int main()
{
// Number of columns must be constant
int const n_columns(20);
// But number of rows can be variable
int n_rows( getNumberOfRows() );
// Declare a pointer to array of rows of 20 columns and
// create a 2D array of the compatible dimensions.
// Note that the n_columns value appears in the pointer type declaration as
// well as the new [] expression.
Element (* two_d_of_element)[n_columns] = new Element[n_rows][n_columns];
// Destroy the elements (which displays the i member value for each Element destroyed)
delete [] two_d_of_element;
}
The getNuberOfRows function just returns a fixed value in this example but you could of course get a value from elsewhere - a file, the user etc..:
int getNumberOfRows()
{
return 10;
}
When run the
delete [] two_d_of_element;
line should cause a lines to be output like the following:
Deleting Element #199
Deleting Element #198
Deleting Element #197
Deleting Element #196
Deleting Element #195
Deleting Element #194
Deleting Element #193
Deleting Element #192
Deleting Element #191
Deleting Element #190
. . .
. . .
. . .
Deleting Element #10
Deleting Element #9
Deleting Element #8
Deleting Element #7
Deleting Element #6
Deleting Element #5
Deleting Element #4
Deleting Element #3
Deleting Element #2
Deleting Element #1
Deleting Element #0
Which shows several things:
- All elements of an array are default constructed
- All elements of an array have their destructor called, in reverse order of creation
(note: this is the difference between delete and delete [] - delete only calls the
destructor for a single item)
- The syntax though horrible does indeed refer to an array of 10*20 elements.
- The constant dimension (n_columns) is used as part of the type declaration of the pointer
returned by new [] as well as in the new [] expression itself.
Now if your array contained pointers to Element objects rather than Element objects themselves then we would have to first create the array of pointers, then create a new Element for each (pointer) element in the array. When done we would need to delete each Element pointed to by the pointers in the array and then delete the array of pointers.
First I shall add a getElementNumber member function to Element:
class Element
{
// ...
int getElementNumber() const { return i; };
};
Now for the updated main:
#include <iostream>
int main()
{
// Number of columns must be constant at compile time
int const n_columns(20);
// But number of rows can be variable (obtained at runtime)
int n_rows( getNumberOfRows() );
// Declare a pointer to 2D array of rows of 20 columns of _pointers_ and
// create a 2D array of the same dimensions:
// Element from the previous example has been replaced by Element *
Element * (* two_d_of_element_ptrs)[n_columns] = new Element*[n_rows][n_columns];
// The pointers in the array are initialised to rubbish. We
// have to allocate Element objects for each array element:
for ( int r = 0; r < n_rows; ++r )
{
// Allocate an element for each row,column index pair and
// display the Element's creation number
for ( int c = 0; c < n_columns; ++c )
{
two_d_of_element_ptrs[r][c] = new Element;
std::cout << "Created element #"
<< two_d_of_element_ptrs[r][c]->getElementNumber()
<< '\n';
}
}
// Before deleting the array of pointers we have to
// delete each Element object pointed to:
// (which displays the i member value for each Element deleted)
for ( int r = 0; r < n_rows; ++r )
{
for ( int c = 0; c < n_columns; ++c )
{
delete two_d_of_element_ptrs[r][c];
}
}
// Destroy the Elements pointer array
delete [] two_d_of_element_ptrs;
So after two questions on deleting objects in data structures that contain, own or refer to other dynamically allocated objects I hope you are getting the idea.
I would also suggest you re-read my comments on smart pointers and consider how they could be used in these array contexts. Pay special head to the need for separate array versions of smart pointers (to use delete [] rather than delete).
Finally, I would suggest you look at the C++ standard library. It contains class templates for various containers including list and vector types (vector here means single dimension array). You can of course arrange for a specific vector type to contain other vectors - so you can have a vector of vector of int for example. The advantage of these types is that they take care of most of the housekeeping of memory management for you. A good reference and tutorial is "The C++ Standard Library a Tutorial and Reference" by Nicolai M. Josuttis.
