Lesson # 8. Dynamic memory. Arrays of pointers.

Авторadmin / Опубликовано

Back
Menu
Go ahead

Theory

    Function template

  • A template variable is defined by declaring it before the beginning of a class or function:
    • template <typename T>
int max(T a, T b) {
  if (a > b) { return a; }
     return b;
}
  • Templated variables are checked at compile time, which allows for errors to be caught before running the program.
    • #include <iostream>
using namespace std;
 
template <typename T>
T max(T a, T b) {
	if (a > b) { return a; }
	return b;
}
int main()
{
	cout << "max(3, 5): " << max(3, 5) << endl; // 5
	cout << "max('a', 'd'): " << max('a', 'd') << endl; // d
	cout << "max(\"Hello\", \"World\"): " << max("Hello", "World") << endl; // Hello
	cout << "max(3, 5, 6): " << max(3, 5, 6) << endl; // error
 
	system("pause");
	return 0;
}
  • A function template defines a family of functions.
  • Function and class templates should be defined only in the header file.

    • lib.cpp

    #include "lib.h"

    lib.h

    template<typename T>
class My
{
    My() { }
T f(T a, T b);
};
 
template<typename T>
T My::f(T a, T b)
{
  return a + b;
}
  • A function template by itself is not a type, or a function, or any other entity. No code is generated from a source file that contains only template definitions. In order for any code to appear, a template must be instantiated: the template arguments must be determined so that the compiler can generate an actual function.
  • An explicit instantiation definition forces instantiation of the function or member function they refer to. It may appear in the program anywhere after the template definition, and for a given argument-list, is only allowed to appear once in the program, no diagnostic required.
    • template<typename T>
void f(T s)
{
    std::cout << s << '\n';
}
 
template void f<double>(double); // instantiates f<double>(double)
template void f<>(char); // instantiates f<char>(char), template argument deduced
template void f(int); // instantiates f<int>(int), template argument deduced
  • Implicit instantiation: When code refers to a function in context that requires the function definition to exist, and this particular function has not been explicitly instantiated, implicit instantiation occurs. The list of template arguments does not have to be supplied if it can be deduced from context.
    • #include <iostream>
 
template<typename T>
void f(T s)
{
    std::cout << s << '\n';
}
 
int main()
{
    f<double>(1); // instantiates and calls f<double>(double)
    f<>('a'); // instantiates and calls f<char>(char)
    f(7); // instantiates and calls f<int>(int)
    void (*ptr)(std::string) = f; // instantiates f<string>(string)
}

    1. A pointer to a one-dimensional array in dynamic memory

    int* p = new int[10];
for (int* q = p; q<p+10; q++)
  *q = 1;
 
for (int i=0; i<10; i++)
  p[i] = 1;
 
delete [] p;

    For simple types, you can write delete p (the runtime subsystem knows that we allocated an array), but for classes this is an error.

    Errors related to using of dynamic memory

    Error 1. Accessing a section of dynamic memory that we have already returned using delete

    int* p = new int;
*p = 777;
delete p;
*p = 666;
  • What to do?:
    • int* p = new int;
*p = 777;
delete p;
p = nullptr; // !
*p = 666;
  • Why it’s not enouph?:
    • int* p = new int;
int * q = p;
…
delete p;
p = nullptr; // !
*q = 666;
  • Error 2. We returned dynamic memory twice using delete
    • int* p = new int;
*p = 777;
delete p;
…
delete p;
  • Error 3. Dynamic memory leak
    • int* p = new int[1000];
*p = 777;
…
// and forgot to delete!
  • Error 3a. Dynamic memory leak in the loop
    • for (int i = 0; i<100000; i++)
{
  int* p = new int[1000];
  *p = 777;
  …
  // and forgot to delete!
 
}
  • Error 3b. Dynamic memory leak in the function.
    • void p()
{
  int* p = new int[1000];
  *p = 777;
  …
  // and forgot to delete!
}
  • The rule. If dynamic memory is allocated in a function, then it must be returned in the same function. There are exceptions.

    • Two-dimensional arrays

  • A two-dimensional array is considered as a one-dimensional array of one-dimensional arrays
    • int a[3][4];
  • Two-dimensional rectangular arrays («matrices») are conveniently modeled using pointer arrays:
    • int ** mat = new int *[rows]; // future matrix of rows of rows

    Each element mat[i] of this array is a pointer, it should be initialized in a loop, assigning it the result new int [cols], where cols is the desired number of columns of the matrix.

  • The reference to the (i, j)-th element of the matrix looks like this: mat[i][j]. To iterate over the matrix, just as in the case of a regular array, you can use pointers.
  • It is necessary to empty (devastate) memory, it should be done in the reverse order: first, the memory for each row is released in the loop: delete [] mat[i]. And then the memory of the array of pointers mat: delete [] mat is released. This procedure should be executed as a function with one argument rows(number of rows).

    • Another example:

  • This is an array of three elements of type int [4] 
    • a[i][j] ~ *(a[i] + j) ~ *(*(a + i) + j)

    Printing an array:

    void print(int a[][4], int m, int n)
{
  for (int i=0; i<m; i++)
  {
    for (int j=0; j<n; j++)
    cout << a[i][j] << " ";
    cout << endl;
  }
}

    Two-dimentional arrays and dynamic memory

  • In order to pass a two-dimensional array of arbitrary dimension to a function, it should be allocated in dynamic memory:
    • void print(int** a, int m, int n)
{
  for (int i=0; i<m; i++)
  {
    for (int j=0; j<n; j++)
    cout << a[i][j]; // a[i][j] ~ *(*(a + i) + j)
    cout << endl;
  }
}
int main()
{
// allocation in memory
  int** p = new int*[3]; // pointer pointing to pointer (3 rows)
  for (int i=0; i<3; i++)
     p[i] = new int[4]; // 4 columns
  print(p,3,4);
  …
}
  • After using it in the function, the allocated memory must be returned:
    • int main()
{
  int** p = new int*[3];
  for (int i=0; i<3; i++)
    p[i] = new int[4];
 
print(p,3,4); // Нарисовать на доске
// deallocation of memory:
for (int i=0; i<3; i++)
  delete [] p[i];
delete [] p;
p = nullptr;
}

    Stepwise two-dimensional dynamic arrays

    int main()
{
  int** p = new int*[3];
 
  for (int i=0; i<3; i++)
    p[i] = new int[4];
 
  print(p,3,4);
  for (int i=0; i<3; i++)
    delete [] p[i];
  delete [] p;
  p = nullptr;
}

Labs and Tasks

1. One-Dimensional Array In Dynamic Memory

Lab 1:
To do: Create a solution with two function templates. One of them inputs the elements of a one-dimensional array of a specified size, the other outputs the elements of a one-dimensional array of a given size. It is possible to create all the code in the main cpp file. Input and output the array elements of double type.

Note: The signature of the function templates should be as following:

template <typename T> 
void inputArr(T* arr, int &size);
 
template <typename T>
void printArr(const T* arr, int &size);

Expected output:

Lab 1:
Array[0] 1.1
Array[1] 2.1
Array[2] 3.2
Array[3] 4.1
Array[4] 5.4

1.1 2.1 3.2 4.1 5.4

✍ How to do:

  • To perform the lab, create an empty console application with a name Lesson8. Add file: L8Lab1main.cpp.
  • Include all the necessary libraries.
  • Create int main function that returns 0.
  • Above the main function, add the function template code for entering the elements of an array. The function will have two parameters — a pointer to the array and a reference to a variable that stores the size of the array.
    • template <typename T> 
void inputArr(T* arr, int &size) { // arr is a pointer to the array of any type
	for (int i = 0; i < size; i++) {
		cout << "Array[" << i << "] ";
		cin >> arr[i]; // dereference of the pointer arr
	}
}
  • In the main function, initialize the variable that stores the size of the array (the array will have 5 elements), and declare a pointer to a new array of double type:
    •   int size = 5;
  double* myArray = new double[size];
  • Call the function:
    • inputArr(myArray, size);
  • Above the main function, add the function template code to output the elements of the array:
    • template <typename T>
void printArr(const T* arr, int &size) {
	for (int i = 0; i < size; i++) {
		//cout << arr[i] << " "; // dereference way 1:
		cout << *(arr + i) << " "; //dereference way 2:
	}
}
    Use one of two ways to dereference the pointer.
  • Call the function in the main method:
    • printArr(myArray, size);
  • Once the dynamic array is allocated in the memory, it must be deallocated. Let's deallocate the array in the main:
    • delete[]myArray;
myArray = NULL;
    After the delete operator, the myArray pointer is allocated to something that doesn't belong to our program. To prevent the array of pointers from pointing to any address, you must assign a NULL value.
  • Run the program.
Task 1:

To do: An array of integers (A) is given. Create an array in which the number 0 is inserted instead of the elements, the last digit of which is equal to 0. In this task, you need to use dynamic memory (new / delete). Make a template function to print the array.

Note 1: Make sure that in the main program, after printing the resulting array, you did not forget to deallocate memory (delete []).

Note 2: The signature of the function should be as follows:

void MakeArrayWithZero(int* a, int& size);

Where a is a given array, and size is a size of the array.

Note 3: Template function to print the array must be in header file and have the following signature:

template<typename T>
void printArray(T const * arr, int size, char delim = ' ') {
  ...
}

Expected output:

Task 1:
Array before the task is done:
1 20 30 4 5 
Result:
1 0 0 4 5

[Solution and Project name: Lesson_8task1, file name L8Task1main.cpp, L8Task1imp.cpp, L8Task1.h]

Task 2:

To do: An integer array is given. Сreate a new array, based on the given one, in which all occurrences of a given number are deleted. The original array does not change. You shouldn't use here any standard function.

Note 1: First, it is better to calculate the number of elements of the new array, and then create a new array with the specified number of elements. To do this, use a function with the following signature:

int* delete_all_entries(int* a, int size, int n, int& new_size)

Note 2: Create template function to print out the array elements. Use the following signature:

template<typename T>
void print_array(T const* a, int size, char delim = ' ');

Expected output:

Task 2:
original array:
1 2 3 2
number to be deleted:
2
new array:
1 3

[Solution and Project name: Lesson_8task2, file name L8Task2main.cpp, L8Task2imp.cpp, L8Task2.h]

Two-dimensional arrays

Lab 2:

To do: Define the function for creating a matrix of specified dimensions, all elements of which are equal to a given number:
header file:

int ** createMatrix(int rows, int cols, int value = 0);

The default value of 0 for the value parameter should be specified only in the header file. In the cpp file, the header contains three parameters in the usual form:
implementation file:

int ** createMatrix(int rows, int cols, int value) {
}

The default value indicates that the function can be called with two arguments, then the value of the value parameter will be the number 0.

Note: To print the matrix you should create one more function with a signature:

void printMatrix(int ** mat, int rows, int cols);

Expected output:

Lab 2:
matrix 5 by 5:
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0

[Solution and Project name: Lesson_8Lab2, file name L8Lab2main.cpp, L8Lab2imp.cpp, L8Lab2.h]

✍ How to do:

  1. To perform the lab, create an empty console application with a name Lesson8Lab2.
  2. Include all the necessary libraries and header file.
  3. Since we must create a matrix in the function, let's start with a function code. Open the header file and add the signature of the function:
    4. #pragma once

#ifndef HEADER_H
#define HEADER_H

int ** createMatrix(int rows, int cols, int value = 0);

#endif
  4. Then, open the implementation file and add the function:
    5. // ...
int ** createMatrix(int rows, int cols, int value) {
  //...
}
  5. First of all, we should allocate the memory for our two-dimensional array (matrix). To do it, add the code into the function:
    6. int** res = new int*[rows];
for (int i = 0; i < rows; i++)
	{
		res[i] = new int[cols];
		for (int j = 0; j < cols; j++) {
			res[i][j] = value;
		}
	}
    In the first line we declare a pointer that points to the addresses of rows which are the pointers themselves pointing to the addresses of columns. So we allocate the memory for the matrix.
    In the line #4 for each row we allocate the memory for the columns. The number of rows and columns we take from the arguments.
  6. The function will return the matrix, so add the code:
    7.   return res;
} // end of function scope
  7. Now, we can turn to the main file and ain function to call this function we've created.
  8. Since our function will return a created matrix, we should create a variable to store that matrix and assign the result of our function to it.
    9. int main() {
  // create a matrix with 4 rows and 5 columns each element equals 0:
  int** matrix = createMatrix(4, 5, 0);
  //...
}
  9. Try to run the program and make sure that there are no errors.
  10. After, we're going to create a function to output the elements of the matrix. There will be three arguments there - to accept the matrix itself and the number of columns and rows. Add the code into the implementation file:
    11. void printMatrix(int ** mat, int rows, int cols) {
	for (int i = 0; i < rows; i++) {
		for (int j = 0; j < cols; j++) {
			cout << mat[i][j] << " ";
		}
	cout << endl;
	}
}
  11. Add the signature of the function into header file. Do it yourself.
  12. Run the program and make sure that there are no errors.
  13. Once a dynamic array was created, we should deallocate the memory when the task with that array is done. Let's create a function to deallocate the memory. Add the code of the function:
    14. void freeMemory(int ** mat, int rows) {
	for (int i = 0; i < rows; i++) {
		delete[] mat[i];
	}
	delete[] mat;
	mat = NULL;
}
    Since we need to use the pointers, we should know the number of rows only, it is passed in from the main program as argument.
  14. Add the signature of the function to the header file and call the function in the main source file.
Task 3:

To do: Create a function to find the minimum and maximum values of the matrix. To do the task you can use the similar functions from lab # 2 (to create a matrix, to print it out and to deallocate the memory). The elements of the matrix must be randomly generated. The signature of the function to find min and max should be as follows:

void matrixMinMax(int ** mat, int rows, int cols, int &min, int &max);

Note: to have randomly generated elements you should include the following library:

#include <ctime>
// ...
srand(time(0));
//.. inside nested loops:
array_name[i][j] = 1 + rand() % 10;

Expected output:

Task 3:
matrix 4 by 5:
5 4 0 7 0
0 8 0 1 2
0 5 0 7 0
4 0 0 9 0

max = 9  min = 0

[Solution and Project name: Lesson_8task3, file name L8Task3main.cpp, L8Task3imp.cpp, L8Task3.h]

Task 4:

To do: A square matrix of integer elements is given. Calculate the sum of the elements of its main diagonal. Make sure that in the main program, after the matrix returned by functions is no longer needed, the corresponding memory is freed.

Expected output:

Task 4:
matrix:
8 3 3 6
6 4 9 8
6 1 9 6
4 5 1 5

sum = 26

[Solution and Project name: Lesson_8task4, file name L8Task4main.cpp, L8Task4imp.cpp, L8Task4.h]

Back
Menu
Go ahead