Pointers and Dynamic Arrays



Download 225.1 Kb.
Page3/4
Date05.08.2017
Size225.1 Kb.
#26675
1   2   3   4
10.2 Dynamic Arrays

Array Variables and Pointer Variables , Creating and Using Dynamic Arrays
This section introduces the dynamic array concept. A dynamic array is an array that is allocated on the free store in amounts that may be determined by the program. These ideas can be used to implement a dynamic array of any base type. More usefully, we could implement a dynamic array class.
The critical issues in this section are the allocation of free store (or heap) memory and the deallocation of the memory once the program is through with it.
int *p = new int[10];

int q[10];


When these variables go out of scope, the memory allocated for q is released. There are three differences between these two declarations.

  • The first difference is that only the memory allocated (on the stack) for p, is released, but the memory allocated (on the free store) by new that p to points to is not released. The memory allocated by new is orphaned if not deallocated with delete. It can never be retrieved by this program, and will only be available to other programs after the program terminates.

  • The second difference is that the sizeof operator11 gives different results applied to p and to q. The sizeof operator has not been discussed so far in the text. The value of sizeof p is the size of an int pointer, sizeof (int*), whereas sizeof q is 10 * sizeof int. Why? The variable p is a pointer, and q is an array. Yet, q carries the same address information that p does, but they are subtly different.

  • The third difference is discussed in the text. You can assign to p, but not to q. In other words, an array name is not an l-value. A pointer variable is an l-value.

The text presents a dynamic array in Display 10.7, A Dynamically Allocated Array. Here, space is allocated as specified at runtime. (Ordinary arrays require that the size be known at compile time.) In this program, there are three points.



  • The typedef (first line after the #include statements) makes IntArrayPtr behave as a 'super' int*,

  • The new statement (line 22, in the main function) allocates the requested amount of memory, and

  • The delete statement syntax must be:

delete [] pointerVariable;.

Note that the variable, pointerVariable, must point to memory allocated with new Type[size].

Note that the functions fillArray and sort ask for ordinary array parameters and accept the pointers as array parameters.
In programming languages, a first class type is a type that can be used exactly like the primitive types (char, short, int, long, float, double, etc). This means that the first class type can be a class or struct member type, a function parameter type, a function return type, and a base type for an array. An array type fails the function return type test. An array cannot be a function return type. Arrays also fail the function parameter test.

When passed to a function, an array deteriorates to pointer to base type. The size information is lost. Consequently, all C++ passes to an array parameter is the address of the array. The programmer must tell the function other information: the base type is specified in the declaration of the array formal parameter and the size is passed in the int formal parameter.


Example: A Function that Returns an Array

This is illegal. The return type must be a pointer to an array’s base type, and have value pointing to the array’s first element to carry this out. Care must be exercised to ensure that the pointer does not point to an object that has a short life time or otherwise be destroyed when the returned value is used.


Pointer Arithmetic

Pointer arithmetic is scaled. This means that when 1 is added to a pointer value, ptr, the result is a pointer that points to the next object in memory beyond where the pointer originally pointed. What happens is that the numeric value of the pointer has sizeof(type) added to the pointer. If some other int value, say k, is added to a pointer value, the result is a pointer that points to the kth object beyond where the original pointer pointed. The value of the resulting pointer expression is the original numeric value of the pointer with the value, k* sizeof(type).


Multidimensional Dynamic Arrays

Here is a body of code from which I learned a lot about dynamically allocated multidimensional arrays and the use of nested vector types to implement this data type.


Ideas here are heavily modified from this URL:

http://www.cplus-zone.com/free/articles/toptips/toptips6.asp#tip19


#include

#include

#include

using namespace std;


vector >

operator+(const vector >& lhs,

const vector >& rhs);
vector >

operator+(const vector >& lhs,

const vector >& rhs)

{

unsigned int i, j;



//declare and allocate rows

vector > sum; /* two dimensions */

// create rows 0 through 4, rows have zero size

for(i = 0; i < 5; i++)

sum.push_back(vector ());
// check number of rows

if(lhs.size() != rhs.size())

{

cout << "size of lhs != size of rhs. Aborting!\n";



abort();

}
//check the row lengths.

for(i = 0; i < lhs[i].size(); i++)

{

if(lhs[i].size() != rhs[i].size())



{

cout << "size of lhs[" << i << "]"



<< " != size of rhs[" << i << "]. Aborting!\n";

abort();


}

}
for(i = 0; i < lhs.size(); i++)

{

for(j = 0; j < lhs[i].size(); j++)



sum[i].push_back(lhs[i][j] + rhs[i][j]);

}

return sum;



}
int main()

{

int i, j; //These are use as "for loop" control



//variables. We must declare them outside block

//to avoid multiply defined for "for loop"

//variables when compiling with MS VC++ 6.0.

//Example using int variables and dynamic allocation

double *ppd [5];
//In this code, the parentheses around the *ppd are required

//for double (*ppd)[5] to be parsed as a declaration of ppd

//as pointer to an array of double rather than an array of

//pointers to double. (*ppd)[0] is a pointer to an array

//of double. We can allocate in pieces that will not //(necessarily) be in contiguous memory
ppd[0] = new double[3];

ppd[1] = new double[3];

ppd[2] = new double[3];

ppd[3] = new double[3];

ppd[4] = new double[3];
/* We could assign each component individually

ppd[0][0] = 1;

ppd[1][1] = 1;

ppd[2][2] = 1;

ppd[3][3] = 1;

ppd[4][4] = 1;

*/
// But we may (more flexibly) assign in nested loops.

for(i = 0; i < 5; i++)

for (j = 0; j < 3; j++)

ppd[i][j] = i + j;


for(i = 0; i < 5; i++)

{ cout << " ";

for (j = 0; j < 3; j++)

cout << ppd[i][j] << " ";

}
cout << "finished output" << endl;

cout << "deleting memory" << endl;


// Deleting this requires 5 delete statements.

for(i = 0; i < 5; i++)

delete [] ppd[i];
//Or we can allocate in contiguous memory:

double (*ppd1) [5]=new double[4][5]; // fill array contiguously.


//assign some members

ppd1[0][0] = 6.5;

ppd1[0][1] = 6.6;

ppd1[0][2] = 6.7;


//then use them

//and delete them.

delete [] ppd1;

//This will properly deallocate memory that is allocated in

//this manner.
//However, this style is tedious and error prone. You must

//parenthesize ppd to ensure that the compiler parses the

//declaration correctly, and you must delete the allocated

//memory. Worse, you can easily cause buffer overflows,

//writing to memory beyond what has been reserved for our

//use.
//Using a vector of vectors to simulate a multidimensional

//array is a significantly better alternative:
vector > v; /* two dimensions */

// create rows 0 through 4, rows have zero size

for(i = 0; i < 5; i++)

v.push_back(vector ());


vector > v1; /* two dimensions */

// create rows 0 through 4, rows have zero size

for(i = 0; i < 5; i++)

v1.push_back(vector ());


cout << v.size() << " ";
for(i = 0; i < 5; i++)

cout << v[i].size() << " ";

cout << endl;
//insert some values in the array

for(i = 0; i < 5; i++)

for(j = 0; j < 4; j++)

v[i].push_back(2*i+j);


for(i = 0; i < 5; i++)

for(j = 0; j < 4; j++)

v1[i].push_back(3);
//Because vector overloads operator[], you can use the [][]

//notation as if you were using a built-in two-dimensional array:


cout << v[0][0] << " "

<< v[1][0] << endl;
for(i = 0; i < 5; i++)

{

for(j = 0; j < 4; j++)



cout << v[i][j] << " ";

cout << endl;

}

cout << endl;



vector > sum;
sum = v + v1;
for(i = 0; i < 5; i++)

{

for(j = 0; j < 4; j++)



cout << v1[i][j] << " ";

cout << endl;

}

cout << endl;


for(i = 0; i < 5; i++)

{

for(j = 0; j < 4; j++)



cout << sum[i][j] << " ";

cout << endl;

}

cout << endl;


return 0;

}
The main advantages of using a vector of vectors are:



  • The STL vector automatically allocates memory as needed.

  • The STL vector takes care of deallocating memory so you don't have to worry about memory leaks.





Download 225.1 Kb.

Share with your friends:
1   2   3   4




The database is protected by copyright ©ininet.org 2024
send message

    Main page