CS250 - Data Structures & Algorithms
Lecture 2: Review C++ (Pointers & Dynamic
Memory Allocation)
Dr. Muhammad Shahzad
[Link]@[Link]
Department Of Computing (DOC),
School of Electrical Engineering & Computer Science (SEECS),
National University of Sciences & Technology (NUST)
15/10/2020
Recap slide
▪ Data Structure is a systematic way to organize data in order
to use it efficiently
▪ An algorithm is an effective method for solving a problem
using a finite sequence of instructions
▪ Data types:
► Primitive Data Types
- Bool, Int, float etc.
► User-Defined Data Types (UDTs)
- Aggregate data types e.g., structures, array-of-integers etc.
► Abstract Data Types (ADTs)
- Does not specify how the data type is implemented
- In an object-oriented language such as C++, an ADT and its
implementation together make up a class
M. Shahzad: Data Structures & Algorithms Lecture 2: Review C++ (Pointers and dynamic memory allocation) 2
Today‘s lecture
▪ Pointers
▪ Referencing vs pointers
▪ Arrays & dynamic memory allocation
▪ Stack vs heap
▪ The new operator & memory leaks
▪ Concept of shalow/deep copying
▪ Void pointer
M. Shahzad: Data Structures & Algorithms Lecture 2: Review C++ (Pointers and dynamic memory allocation) 3
Pointers
M. Shahzad: Data Structures & Algorithms Lecture 2: Review C++ (Pointers and dynamic memory allocation) 4
Pointers
M. Shahzad: Data Structures & Algorithms Lecture 2: Review C++ (Pointers and dynamic memory allocation) 5
Pointers
M. Shahzad: Data Structures & Algorithms Lecture 2: Review C++ (Pointers and dynamic memory allocation) 6
Pointers
M. Shahzad: Data Structures & Algorithms Lecture 2: Review C++ (Pointers and dynamic memory allocation) 7
Pointers
M. Shahzad: Data Structures & Algorithms Lecture 2: Review C++ (Pointers and dynamic memory allocation) 8
Pointers
M. Shahzad: Data Structures & Algorithms Lecture 2: Review C++ (Pointers and dynamic memory allocation) 9
Pointer example
M. Shahzad: Data Structures & Algorithms Lecture 2: Review C++ (Pointers and dynamic memory allocation) 10
Pointer example
M. Shahzad: Data Structures & Algorithms Lecture 2: Review C++ (Pointers and dynamic memory allocation) 11
Pointer example
M. Shahzad: Data Structures & Algorithms Lecture 2: Review C++ (Pointers and dynamic memory allocation) 12
Differences between references & pointers
▪ Consider the following declarations:
int n=5, *p = &n, &r = n;
▪ A reference variable must be initialized in its declaration as a
reference to a particular variable, and this reference cannot be
changed, meaning that a reference variable CANNOT be null
▪ A reference variable r can be considered a different name for a
variable n
► If n changes then r changes as well. This is because a reference
variable is implemented as a constant pointer to the variable
▪ cout << n << ' ' << *p << ' ' << r << endl;
*p = 9;?
Output: 5 5 5 r = 10;?
M. Shahzad: Data Structures & Algorithms Lecture 2: Review C++ (Pointers and dynamic memory allocation) 13
Constant pointer vs pointer constant
▪ The declaration int& r = n; actually can be replaced by
int *const r = &n;
where r is a constant pointer to an integer, which means that
the assignment r = q; where q is another pointer, is an error
because the value of r cannot change
▪ However, the assignment *r = 1; is acceptable if n is NOT a
constant integer
▪ It is important to note the difference between the
type int *const and the type const int *
where const int * is a type of pointer to a constant integer:
const int * s = &m;
after which the assignment s = &m; where m is an integer
(whether constant or not) is admissible, but the assignment
*s = 2; is erroneous, even if m is not a constant
M. Shahzad: Data Structures & Algorithms Lecture 2: Review C++ (Pointers and dynamic memory allocation) 14
Array names as pointers
#include <iostream>
void main() {
const SIZE = 5
int i, arr[SIZE] = {98, 87, 92, 79, 85};
for(i=0; i<SIZE; i++)
cout << arr[i] << *(arr + i) << endl;
}
M. Shahzad: Data Structures & Algorithms Lecture 2: Review C++ (Pointers and dynamic memory allocation) 16
String Literals
M. Shahzad: Data Structures & Algorithms Lecture 2: Review C++ (Pointers and dynamic memory allocation) 17
Pointers & Arrays
M. Shahzad: Data Structures & Algorithms Lecture 2: Review C++ (Pointers and dynamic memory allocation) 18
Pointers: function arguments
M. Shahzad: Data Structures & Algorithms Lecture 2: Review C++ (Pointers and dynamic memory allocation) 19
Pointers: function arguments
M. Shahzad: Data Structures & Algorithms Lecture 2: Review C++ (Pointers and dynamic memory allocation) 20
Today‘s lecture
▪ Pointers
▪ Referencing vs pointers
▪ Arrays & dynamic memory allocation
▪ Stack vs heap
▪ The new operator & memory leaks
▪ Concept of shalow/deep copying
▪ Void pointer
M. Shahzad: Data Structures & Algorithms Lecture 2: Review C++ (Pointers and dynamic memory allocation) 21
Dynamic memory allocation
▪ Arrays are useful, however we must know in advance about
the amount of memory required
▪ In many situations, we do not know exact size required until
runtime
▪ Reserving maximum wastes memory
▪ Here comes the concept of dynamic memory allocation
M. Shahzad: Data Structures & Algorithms Lecture 2: Review C++ (Pointers and dynamic memory allocation) 22
Dynamic memory allocation
▪ To avoid wasting memory, array allocation or deallocation
can take place at run time
▪ To allocate memory, we need to use the new operator
► Reserves the number of bytes requested by the declaration
► Returns the address of the first reserved location or NULL if
sufficient memory is not available
▪ To deallocate memory (which has previously been allocated
using the new operator) we need to use the delete operator
► Releases a block of bytes previously reserved. The address of
the first reserved location is passed as an argument to delete.
M. Shahzad: Data Structures & Algorithms Lecture 2: Review C++ (Pointers and dynamic memory allocation) 23
The new operator
▪ new keyword obtains memory from OS and returns a
pointer to starting location
int x = 10;
int *ptr;
ptr = new int;
*ptr = x;
cout<<*ptr;
M. Shahzad: Data Structures & Algorithms Lecture 2: Review C++ (Pointers and dynamic memory allocation) 24
Memory leaks – delete operator
▪ If your program reserves many chunks of memory using new,
eventually all the available memory will be reserved and system
will crash
▪ To ensure safe and efficient use of memory, new is matched by a
corresponding delete
▪ If the program terminates the memory is released automatically,
however, if a function allocates memory using new and doesn't
release it then the pointer is destroyed but not the memory which
causes waste of memory
▪ E.g., consider two lines of code Correct should be
p = new int;
p = new int;
p = new int;
delete p;
where after allocating one cell for an integer, p = new int;
the same pointer p is used to allocate another cell
M. Shahzad: Data Structures & Algorithms Lecture 2: Review C++ (Pointers and dynamic memory allocation) 25
Case of 1D array
cout << "Enter array size: ";
cin >> SIZE;
int *arr;
arr = new int[SIZE]; // allocation
delete [] arr; // deallocation
M. Shahzad: Data Structures & Algorithms Lecture 2: Review C++ (Pointers and dynamic memory allocation) 26
