Pointers Part II (Dynamic Memory Allocation) Allocation) Lecture 13 Copyright (C) 2004 by Wong Ya Ping updated : ver080916(KCLee) Computer Programming. - презентация

1 Pointers Part II (Dynamic Memory Allocation) Allocation) Lecture 13 Copyright (C) 2004 by Wong Ya Ping updated : ver080916(KCLee) Computer Programming I

2 Lecture Objectives To understand how to allocate memory dynamically during runtime. To understand the difference between static array and dynamic array. 2

3 3 Review on Pointers p + i&p[i] equivalent *(p + i)p[i] equivalent Given a pointer or an array p of any data type and an integer i : Thus also: p == &p[0]*p == p[0] You need to be absolutely sure about this!

4 4 Review Question Discuss the output of the following program. #include using namespace std; int main() { int a[] = {11, 22, 33, 44, 55}; int x; int *p = a; x = *p++; cout<< "*p = " << *p <<"\n\n"; cout<< "x = " << x <<"\n\n\n"; int b[] = {11, 22, 33, 44, 55}; int y; int *q = b; 4 y = (*q)++; cout<< "*q = " << *q <<"\n\n"; cout<< "y = " << y <<"\n\n\n"; int c[] = {11, 22, 33, 44, 55}; int z; int *r = c; z = *++r; cout<< "*r = " << *r <<"\n\n"; cout<< "z = " << z <<"\n\n\n"; cout << "\n\n"; system("pause"); return 0; }

5 5 Static Memory Allocation So far, the definition and declaration of all our variables and arrays and their memory sizes are fully specified in our program during compile time. When the program runs, memory is allocated upon the execution of the function and remain allocated during the lifetime of the function. The memory reserved for these variables and arrays cannot be changed by the program during run time. This is called Static Memory Allocation or Automatic Memory Allocation Take note that the size of arrays must be determined during compile time and our program cannot change the size of the arrays. #include using namespace std; int main() { int m[5], count = 0; bool done= false, full= false; do { cin >> m[count]; if ( m[count] == -1 ) { done = true; count--; } if ( count == 4 ) { cout << "Memory full!\n"; full = true; } count++; } while ( !done && !full ); for (int i=0; i < count; i++) cout << m[i] << " "; }

6 6 The question arises: What if we can only determine the size of the array during run time? The strategy so far is to set the size of the array big enough that perhaps the size may never reach that number. This may not work all the time, if we need bigger array, we need to change it in our program and recompile the program. One possible solution is to use the STL's vector class taught previously. The STL's vector is a built-in library class, what mechanism is this class using to incorporate the ability to resize the array on demand?

7 7 Take note that, so far, all our pointers point to some other variables or arrays. In fact, C allows us to allocate memory during run- time and makes our pointer points to that memory. This is called Dynamic Memory Allocation (DMA). In fact, this is the major use of pointers! int main() { int m[10]; float k; int* p; float* q; p = m; q = &k;... } Dynamic Memory Allocation (DMA)

8 int* p; p = new int; 8 To dynamically allocate memory for one integer value: The allocated memory can only be accessed using this pointer. The new operator dynamically allocates enough memory to store one int value, it returns the address (a pointer of type [int *]) of the memory allocated p [ int* ] ?? Note that there is no variable associated with the memory allocated, thus the only way to access this memory is via the pointer p which stores the address of this memory.

9 9 Heap Memory and Stack Memory When we allocate memory using the new operator, memory are allocated to be used by our program from the pool of memory called Heap or Freestore. Heaps are used to contain all our dynamically allocated memory. The heap maintains a freelist (list of all the free memory available) and when we allocate and deallocate memory, it updates this free list. On the other hand, the Stack memory is where the run-time values, local variables, parameters, return values etc. are stored. KC Lee: Not crucial – just for knowledge. KC Lee: Not crucial – just for knowledge.

10 10 int* p; p = new int; *p = 47; delete p; p = NULL; Freeing an allocated memory : To free or delete the memory means to deallocate the memory and returns the memory to the pool of available memory in the heap to be used by other requests for memory allocation. If you assign the pointer to have another address before freeing up the allocated memory, the memory will be lost, this results in Memory Leak, your system will report "Out of Memory" if too many memory leak occurred p[ int* ] When the memory is being freed, the pointer will still contain the address value, This is called a Dangling Pointerit is what the pointer pointed to are being freed but NOT the pointer itself. It is a logical error and DANGEROUS if you continue to use this dangling pointer to access the memory since the data may be destroyed if it is being allocated to another pointer later. It is a good practice to assign NULL to a pointer after the memory it is pointing to has been freed / deleted. We use the delete operator here.

11 11 Dynamic One-Dimensional Array There is really not much use if we are just allocating one single value dynamically. The real power of dynamic memory allocation is the ability to allocate arrays dynamically. int* p; p = new int[4]; Allocate memory enough to store an array of 4 integers. The name of the operator is actually new[] and NOT new FA0 p [ int* ] [int]

12 12 int* p; p = new int[4]; p[0] = 13; p[1] = 42; p[2] = 15; p[3] = 32; Since p is now pointing to the address of the first byte of the block of memory allocated and also that p is of type [ int * ], p can now be used just like an array. Therefore p is now a dynamically allocated array and is called a dynamic array FA0 p [ int* ] Accessing Allocated Memory : [int]

13 13 int* p; p = new int[4]; p[0] = 13; p[1] = 42; p[2] = 15; p[3] = 32;... delete[] p; FA0 p [ int* ] Freeing / Deleting allocated memory : It is always a good practice to write the delete[] operator right after you wrote the new[] operator statement. You might forget about it later! To free / delete the dynamic array, we use the delete[] operator and NOT the delete operator, you only need to use this operator once for a whole dynamic array

14 14 NULL 1FA0 p [ int* ] Clearing the pointer : After the memory has been deleted, it is always a good practice to clear the dangling pointer by setting it to NULL. NULL usually has a value of zero int* p; p = new int[4]; p[0] = 13; p[1] = 42; p[2] = 15; p[3] = 32;... delete[] p; p = NULL;

15 15 #include using namespace std; int* resizeArray(int* m, int oldsize, int newsize ) { cout << "resizing array..."; int* p = new int[newsize]; for (int i=0; i < oldsize; i++) p[i] = m[i]; delete[] m; return p; } int main() { int* m; int num, count = 0,capacity = 5; m = new int[capacity]; do { cin >> num; if (num != -1) { if (count == capacity ) { m = resizeArray(m, capacity, capacity+5); capacity += 5; } m[count] = num; count++; } } while ( num != -1 ); for (int i=0; i <= count-1; i++) cout << "m[" << i << "]=" << m[i] << endl; delete[] m;; } Example (Resize the dynamic array): resizing array resizing array... 6 m[0]=8 m[1]=3 m[2]=2 m[3]=7 m[4]=5 m[5]=4 m[6]=3 m[7]=7 m[8]=4 m[9]=2 m[10]=1 m[11]=6 sample run : > num; if (num != -1) { if (count == capacity ) { m = resizeArray(m, capacity, capacity+5); capacity += 5; } m[count] = num; count++; } } while ( num != -1 ); for (int i=0; i <= count-1; i++) cout << "m[" << i << "]=" << m[i] << endl; delete[] m;; } Example (Resize the dynamic array): 8 3 2 7 5 4 resizing array... 3 7 4 2 1 resizing array... 6 m[0]=8 m[1]=3 m[2]=2 m[3]=7 m[4]=5 m[5]=4 m[6]=3 m[7]=7 m[8]=4 m[9]=2 m[10]=1 m[11]=6 sample run :"> 16 #include using namespace std; int* resizeArray(int* m, int oldsize, int newsize) { cout << "resizing array..."; int* p = new int[newsize]; for (int i=0; i < oldsize; i++) p[i] = m[i]; delete[] m; return p; } int main() { int* m; int num, count = 0,capacity = 5; m = new int[capacity]; do { cin >> num; if (num != -1) { if (count == capacity ) { m = resizeArray(m, capacity, capacity+5); capacity += 5; } m[count] = num; count++; } } while ( num != -1 ); for (int i=0; i <= count-1; i++) cout << "m[" << i << "]=" << m[i] << endl; delete[] m;; } 16 Explanation : Initial memory allocation. Calling the resizeArray() function to accommodate more numbers. Allocates enough memory for the new array. Copies the numbers from the old array to the newly allocated array. Makes sure the old array is deallocated! Returns the address of the new dynamic array. > num; if (num != -1) { if (count == capacity ) { m = resizeArray(m, capacity, capacity+5); capacity += 5; } m[count] = num; count++; } } while ( num != -1 ); for (int i=0; i <= count-1; i++) cout << "m[" << i << "]=" << m[i] << endl; delete[] m;; } 16 Explanation : Initial memory allocation. Calling the resizeArray() function to accommodate more numbers. Allocates enough memory for the new array. Copies the numbers from the old array to the newly allocated array. Makes sure the old array is deallocated! Returns the address of the new dynamic array.">

17 17 int arraySize = 4; int* p; p = new int [arraySize];... delete[] p; p = NULL;... One-Dimensional Dynamic Array : Summary :

18 18 Pointer to Pointer Recall that given any data type, the declaration for a pointer to that data will be: datatype * p; So, a pointer to data of type [ int ] will be declared as: int * p; How about a pointer to pointer? just add a ' * ' to the datatype, it will become a pointer to that datatype.

19 19 A pointer to [ int ] has a data type [ int * ], so, A pointer to [ int * ] has a data type [ int * * ], the declaration will be as below: int * * p; p is a pointer The data that p is pointing to has type [ int * ], that means p is pointing to an integer pointer, that means p is a pointer to pointer.

20 20 int m=5, n=6; int *p1, *p2; int **q; p1 = &n; p2 = &n; q = &p1; cout <

21 int m=5, n=6; int *p1, *p2; int **q; p1 = &n; p2 = &n; q = &p1; cout <

22 int m=5, n=6; int *p1, *p2; int **q; p1 = &n; p2 = &n; q = &p1; cout <

23 int m=5, n=6; int *p1, *p2; int **q; p1 = &n; p2 = &n; q = &p1; cout <

24 int m=5, n=6; int *p1, *p2; int **q; p1 = &n; p2 = &n; q = &p1; cout <

25 int m=5, n=6; int *p1, *p2; int **q; p1 = &n; p2 = &n; q = &p1; cout <

26 int m=5, n=6; int *p1, *p2; int **q; p1 = &n; p2 = &n; q = &p1; cout <

27 27 int m = 24; int* p1 = &m; int** q = &p1; Given: m [ int ] 1432 p1 [ int* ] 1542 q [ int** ] We have: q == &p1; *q == p1; *q == &m; Since p1 == &m **q == m; Since for any pointer p, whenever p == &m, then *p = m

28 28 Static Array of Pointers Recall that given any data type, the sample declaration for a static allocated array of that data type will be: datatype p[5]; So, an array of data of type [ int ] will be declared as in example below : int p[5]; How about an array to pointer? The size of the array must be determined during compile time.

29 29 The declaration will be as below: int * q[5]; q is an array. The data type of the array has type [ int * ], that means each element in the array is a pointer, q therefore is an array of pointers.

30 30 int a=1, b=3, c=5; int* q[3]; q[0] = &a; q[1] = &b; q[2] = &c; *q[0] = 9; *q[1] = 7; *q[2] = 2; cout <

31 31 int x[2] = { 2,3 }; int y[3] = { 1,5,7 }; int z = 4; int* q[3]; q[0] = x; q[1] = y; q[2] = &z; q[0][1] = 99; q[1][1] = 55; q[1][2] = 77; q[2][0] = 88; /*same with *q[2]=88*/ cout <

32 [int*] [int*] [int*] q [ int*[] ] z [int] y[0] [int] y[1] [int] y[2] [int] x[0] [int] x[1] [int] int x[2] = { 2,3 }; int y[3] = { 1,5,7 }; int z = 4; int* q[3]; q[0] = x; q[1] = y; q[2] = &z; q[0][1] = 99; q[1][1] = 55; q[1][2] = 77; q[2][0] = 88 Even though q is an array of pointers, from the way it is being used, it looks very much similar to a 2-dimensional array. The number of elements in this array of pointers seems to correspond to the number of rows of this "simulated" 2-D array. The special things about this "simulated" 2-D array is that all the rows do not need to have the same number of columns. Since pointers are often treated like arrays, we can then say that q is an array of arrays (instead of saying array of pointers), in fact 2-D array is often viewed as an array of arrays.

33 33 Dynamic Two-Dimensional Array In the example in previous slides, the number of rows of the "simulated" 2-D array is fixed during compile- time. As for the number of columns for each row, there is some flexibility as we can always assign the pointer to point to any array during run-time. In our example, the arrays these pointers pointed to are all static arrays, this however is not a restriction. Of course, by now, you should know this limitation can be overcome by dynamic memory allocation.

34 34 Before we proceed, lets ask ourselves this question : We know from earlier slides, given an array of int declared with: int m[5]; We can create a pointer to point to it as shown here: int* p; In fact, we can also use this pointer to create a dynamic array like this: int arraySize = 4; int* p; p = new int [arraySize]; The question now is, given an array of pointers such as: int* q[5]; what is the pointer that points to it? How can we create a dynamic array of pointers?

35 35 The answer to the question: int m[5]; Given: Each element is of type int, thus, a pointer to type int is declared as: int* p; SIMILARLY, int* q[5]; Given: Each element is of type int * (pointer), thus, a pointer to type int * is declared as: int** p; This is in fact a pointer to pointers a discussed in the earlier slides.

36 int size = 4; int** q; q = new int* [size]; 36 To dynamically allocate an array of pointers, we use: Here, we dynamically allocate memory using the new[] operator for storing an array of which each element is a pointer of type [int *], in another word, we are allocating memory to store an array of pointers Since each element is of type [int *], the pointer that points to this array is of type [int **].

37 37 int x[2] = { 2,3 }; int y[3] = { 1,5,7 }; int z = 4; int** q; q = new int* [3]; q[0] = x; q[1] = y; q[2] = &z; q[0][1] = 99; q[1][1] = 55; q[1][2] = 77; q[2][0] = 88; /*same with *q[2]=88*/ cout <

38 38 int** q; q = new int* [3]; q[0] = new int [2]; q[1] = new int [3]; q[2] = new int; q[0][0] = 2; q[0][1] = 99; q[1][0] = 1; q[1][1] = 55; q[1][2] = 77; q[2][0] = 88; cout << q[0][0] <<" "<< q[0][1] <

> noOfRows >> noOfCols; q = new int* [noOfRows]; for (int i=0;i<=noOfRows-1;i++) q[i] = new int [noOfCols]; for (int i=0; i <= noOfRows-1; i++) for (int j=0; j <= noOfCols-1; j++) q[i][j] = i*i+j; for (" title="39 int noOfRows,noOfCols; int **q; cout "; cin >> noOfRows >> noOfCols; q = new int* [noOfRows]; for (int i=0;i<=noOfRows-1;i++) q[i] = new int [noOfCols]; for (int i=0; i <= noOfRows-1; i++) for (int j=0; j <= noOfCols-1; j++) q[i][j] = i*i+j; for (" class="link_thumb"> 39 39 int noOfRows,noOfCols; int **q; cout "; cin >> noOfRows >> noOfCols; q = new int* [noOfRows]; for (int i=0;i<=noOfRows-1;i++) q[i] = new int [noOfCols]; for (int i=0; i <= noOfRows-1; i++) for (int j=0; j <= noOfCols-1; j++) q[i][j] = i*i+j; for (int i=0; i <= noOfRows-1; i++) { for (int j=0; j <= noOfCols-1; j++) cout << q[i][j] << " "; cout << endl; } for (int i=0; i <= noOfRows-1; i++) delete[] q[i]; delete[] q; 2-D dynamic array with equal number of columns for each rows : Input => sample run: Make sure the sequence of allocation and deallocation is correct! > noOfRows >> noOfCols; q = new int* [noOfRows]; for (int i=0;i<=noOfRows-1;i++) q[i] = new int [noOfCols]; for (int i=0; i <= noOfRows-1; i++) for (int j=0; j <= noOfCols-1; j++) q[i][j] = i*i+j; for ("> > noOfRows >> noOfCols; q = new int* [noOfRows]; for (int i=0;i<=noOfRows-1;i++) q[i] = new int [noOfCols]; for (int i=0; i <= noOfRows-1; i++) for (int j=0; j <= noOfCols-1; j++) q[i][j] = i*i+j; for (int i=0; i <= noOfRows-1; i++) { for (int j=0; j <= noOfCols-1; j++) cout << q[i][j] << " "; cout << endl; } for (int i=0; i <= noOfRows-1; i++) delete[] q[i]; delete[] q; 2-D dynamic array with equal number of columns for each rows : Input => 5 4 0 1 2 3 1 2 3 4 4 5 6 7 9 10 11 12 16 17 18 19 sample run: Make sure the sequence of allocation and deallocation is correct!"> > noOfRows >> noOfCols; q = new int* [noOfRows]; for (int i=0;i<=noOfRows-1;i++) q[i] = new int [noOfCols]; for (int i=0; i <= noOfRows-1; i++) for (int j=0; j <= noOfCols-1; j++) q[i][j] = i*i+j; for (" title="39 int noOfRows,noOfCols; int **q; cout "; cin >> noOfRows >> noOfCols; q = new int* [noOfRows]; for (int i=0;i<=noOfRows-1;i++) q[i] = new int [noOfCols]; for (int i=0; i <= noOfRows-1; i++) for (int j=0; j <= noOfCols-1; j++) q[i][j] = i*i+j; for (">

40 40 #include using namespace std; float** createArray(int noOfRows, int noOfCols) { float** q = new float* [noOfRows]; for (int i=0; i < noOfRows; i++) q[i] = new float [noOfCols]; return q; } void freeArray(float** q, int noOfRows) { for (int i=0; i < noOfRows; i++) delete[] q[i]; delete[] q; } void displayArray(float** q, int noOfRows, int noOfCols) { for (int i=0; i < noOfRows; i++) { for (int j=0; j < noOfCols; j++) cout << q[i][j] << " "; cout << endl; } Sample Application: Continues... Returns the address of allocated memory

41 41 No of Students => 3 No of Subjects => 4 Student No. 0 Subject 0 mark => 10 Subject 1 mark => 40 Subject 2 mark => 32.2 Subject 3 mark => 50.4 Student No. 1 Subject 0 mark => 23.4 Subject 1 mark => 90.5 Subject 2 mark => 80.4 Subject 3 mark => 30.2 Student No. 2 Subject 0 mark => 90.9 Subject 1 mark => 70.5 Subject 2 mark => 60.4 Subject 3 mark => sample run : …continued from previous page int main() { float** marks; int noOfStudents, noOfSubjects, i, j; cout "; cin >> noOfStudents; cout "; cin >> noOfSubjects; marks = createArray(noOfStudents, noOfSubjects); if (marks != NULL) { for (int i=0; i < noOfStudents; i++) { cout << "Student No. " << i << endl; for (int j=0; j < noOfSubjects; j++) { cout "; cin >> marks[i][j]; } displayArray(marks,noOfStudents,noOfSubjects); freeArray(marks,noOfStudents); } It's a good practice to test if a pointer is NULL before use. > noOfStudents; cout "; cin >> noOfSubjects; marks = createArray(noOfStudents, noOfSubjects); if (marks != NULL) { for (int i=0; i < noOfStudents; i++) { cout << "Student No. " << i << endl; for (int j=0; j < noOfSubjects; j++) { cout "; cin >> marks[i][j]; } displayArray(marks,noOfStudents,noOfSubjects); freeArray(marks,noOfStudents); } It's a good practice to test if a pointer is NULL before use.">

42 42 Pointer Arithmetic and Dynamic 2-D Arrays p + i&p[i] equivalent *(p + i)p[i] Remember that, given a pointer or an array p of any data type : equivalent q[i][j] equivalent ?

43 43 *(q+i)[j] q[i][j] equivalent *( *(q+i) + j ) equivalent q[i][j] *(q+i) + j &q[i][j] equivalent 1402 [int*] [int*] [int*] q [ int** ] z[int] y[0] [int] y[1] [int] y[2] [int] x[0] [int] x[1] [int] *(q+i) &q[i][0] equivalent

44 44 int calSum1( int* q, int n) {... } int calSum2( int q[], int n) {... } int main() { int *q, sum; q = new int[3]; sum = calSum1(q,3); sum = calSum2(q,3);... } int calSum3( int** q, int r, int c) {... } int calSum4( int q[][3], int r, int c) {... } int main() { int **q, sum; q = new int*[4]; for (int i=0; i<4; i++) q[i]=new int[3]; sum = calSum3(q,4,3); sum = calSum4(q,4,3); } Valid INVALID! incompatible type. Function Parameters and Dynamic 2-D Arrays

45 45 void allocate1DArray(int* p, int size) { p = new int [size]; } int main() { int* p; allocate1DArray( p, 10 );... } It won't work, because the value of p (which is an address value) will be copied to the function, but the value of p in the function can never be passed out to main(). Will this function enable us to allocate memory to be used in main()?

46 46 void allocate1DArray(int*& p, int size) { p = new int [size]; } int main() { int* p; allocate1DArray( p,10 );... } There are 3 possible solutions: void allocate1DArray(int** p, int size) { *p = new int [size]; } int main() { int *p; allocate1DArray(&p,10);... } Solution 2: This will work, because we pass the address of pointer p to the function so that the function can modify the value of pointer p (this is the way to do in C, but in C++, it is better to use Solution 1) Solution 1: This will work, because we pass the reference of the pointer p to the function, so whatever changes of p in the function will be reflected in the pointer p in main(). Solution 3: Pass the pointer out as a return value of the function, this is shown in example in earlier slides 16 & 41.

47 End Pointers, References, Dynamic Memory Allocation and Dynamic Memory Allocation are fundamentals concepts of programming. The good understanding of these topics is essential in subsequent course to come such as Computer Programming II, Data Structures & Algorithms, Object-oriented Programming and other programming subjects. May you enjoy programming!...well, you have to....:)