You are here:

C++/deleting multidimensional array pointers

Advertisement


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
--------------------------

000 010 020 030 040 050 060 070 080 090 100 110 120 130 140 150 160 170 180 190
001 011 021 031 041 051 061 071 081 091 101 111 121 131 141 151 161 171 181 191
002 012 022 032 042 052 062 072 082 092 102 112 122 132 142 152 162 172 182 192
003 013 023 033 043 053 063 073 083 093 103 113 123 133 143 153 163 173 183 193
004 014 024 034 044 054 064 074 084 094 104 114 124 134 144 154 164 174 184 194
005 015 025 035 045 055 065 075 085 095 105 115 125 135 145 155 165 175 185 195
006 016 026 036 046 056 066 076 086 096 106 116 126 136 146 156 166 176 186 196
007 017 027 037 047 057 067 077 087 097 107 117 127 137 147 157 167 177 187 197
008 018 028 038 048 058 068 078 088 098 108 118 128 138 148 158 168 178 188 198
009 019 029 039 049 059 069 079 089 099 109 119 129 139 149 159 169 179 189 199


10 rows of 20 elements
----------------------

000 001 002 003 004 005 006 007 008 009 010 011 012 013 014 015 016 017 018 019
020 021 022 023 024 025 026 027 028 029 030 031 032 033 034 035 036 037 038 039
040 041 042 043 044 045 046 047 048 049 050 051 052 053 054 055 056 057 058 059
060 061 062 063 064 065 066 067 068 069 070 071 072 073 074 075 076 077 078 079
080 081 082 083 084 085 086 087 088 089 090 091 092 093 094 095 096 097 098 099
100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119
120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139
140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159
160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179
180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199

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:

Given:

   T cuboidArray[NZ][NY][NX];

   cuboidArray[z][y][x] == *(cuboidArray + (NX*NY)*z + (NX)*y + x)
   
   (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.

Hope this helps.

C++

All Answers


Answers by Expert:


Ask Experts

Volunteer


Ralph McArdell

Expertise

I am a software developer with more than 15 years C++ experience and over 25 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 (although I do not write just-C much if at all these days so maybe ask in the C section about purely C matters), 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 including 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. I have an interest in the development of the C++ core language and libraries and try to keep up with at least some of the papers on the ISO C++ Standard Committee site at http://www.open-std.org/jtc1/sc22/wg21/.

Education/Credentials

©2016 About.com. All rights reserved.