Data Structure and Algorithm Design

Chapter 3

Xingang (Ian) Fang

Sections

  • Memory management

  • Memory management in classes

Memory Management for C++

Xingang (Ian) Fang

Outline

  • Overview

  • Memory Regions

  • Stack

  • Heap

  • Tools

Overview

  • Definition: Memory management in C++ refers to the process of allocating and deallocating memory for objects and data structures during the execution of a C++ program.

  • Motivation

    • Optimizing memory usage

    • Avoiding memory leaks

    • Avoiding dangling pointers

    • Avoiding stack overflow

Memory Regions

Four regions

  • Code: compiled program code.

  • Static: global and static variables

  • Stack: local variables and function parameters

  • Heap: dynamically allocated memory

Memory layout

  • Code and static regions are fixed size and stored in the lower memory addresses.

  • Stack and heap regions are variable size and stored in the higher memory addresses.

  • Stack and heap regions grow towards each other to share free space.

Memory Regions

Credit: https://study.com/academy/lesson/program-memory-in-c-programming.html

Stack Memory Management

  • Stack is a LIFO (Last In First Out) data structure/ADT.

  • The run-time maintains a stack data structure to store local variables and function parameters for function calls.

  • Automatically managed. A.k.a. automatic memory.

  • Stack overflow: when the stack is full and cannot grow further.

    • Caused by infinite recursion or allocating too much memory on the stack.

    • Further discussed in the recursion lecture.

Heap Memory Management

  • Heap is a dynamic data structure/ADT.

  • Managed by the programmer manually.

    • Allocate: new operator

    • Deallocate: delete operator

  • A.k.a. dynamic memory.

  • Variables allocated on the heap are called dynamic data.

  • A pointer variable is the only way to access dynamic data. The pointer is a simple variable that stores the memory address of the dynamic data.

More on Dynamic Data

  • Always remember that the pointer is a separate variable from the dynamic data.

  • The delete operator can take null pointers as arguments. It does nothing but will not cause any problems.

    • It is a waste of time to add if like if (ptr != nullptr) delete ptr;

  • Dynamic variables

    • MyClass *p = new MyClass();

    • delete p;

  • Dynamic arrays

    • Include [] around the operators.

    • int *arr = new int[10];

    • delete[] arr;

Complicated Dynamic Data (FYI)

  • 2D Dynamic array

    int **arr = new int*[10];
for (int i = 0; i < 10; ++i)
    arr[i] = new int[10];
// Use the array
for (int i = 0; i < 10; ++i)
    delete[] arr[i];
delete[] arr;

  • Local array of dynamic arrays as a 2D array

    int *arr[10];
for (int i = 0; i < 10; ++i)
    arr[i] = new int[10];
// Use the array
for (int i = 0; i < 10; ++i)
    delete[] arr[i];

  • Local array of object pointers

    MyClass *myArr[10];
for (int i = 0; i < 10; ++i)
  myArr[i] = nullptr;

int index = 0;
while (true) {
  int value;
  cout << "Enter a value (negative value to exit): ";
  cin >> value;
  ++index;
  if (value < 0 || index >= 10)
    break;
  myArr[index] = new MyClass(value);
}

for (int i = 0; i < 10; ++i)
  delete myArr[i];

  • Dynamic array of object pointers

    MyClass **myArr = new MyClass*[10];
for (int i = 0; i < 10; ++i)
  myArr[i] = nullptr;

int index= 0;
while (true) {
  int value;
  cout << "Enter a value (negative value to exit): ";
  cin >> value;
  if (value < 0 || index >= 10)
    break;
  myArr[index] = new MyClass(value);
}

for (int i = 0; i < 10; ++i)
  delete myArr[i];
delete[] myArr;

Pitfalls

  • Memory leak: Forgetting to deallocate memory

  • Dangling pointer

    • Deallocating memory but still using the pointer

  • Double free

    • Deallocating memory twice

  • Memory access violation: when the program tries to access memory that it does not own. A.k.a. segmentation fault.

    • Invalid pointer

      • Null pointer

      • Uninitialized pointer

      • Assignment of a wrong type (e.g. int) to a pointer

      • Dangling pointer

    • Out-of-bound array access

      • Accessing an array element with an out-of-bound index

      • Accessing an array element with a negative index

Memory Management Tools

  • valgrind is a memory management tool for Linux.

  • valgrind can detect most memory management problems.

  • Unfortunately not natively available on Mac OS.

  • Examples:

    • valgrind --tool=memcheck --leak-check=yes ./main

    • valgrind --tool=memcheck --leak-check=yes --show-leak-kinds=all ./main

    • valgrind --tool=memcheck --leak-check=yes --show-leak-kinds=all --track-origins=yes ./main

  • Read the valgrind memory check manual for more information.

Memory Management in Class Context for C++

Xingang (Ian) Fang

Outline

  • Overview

  • Memory Management in Class Context

  • Ownership of the dynamic data (FYI)

Overview

  • In the class context, because the flow of the program is not linear, the memory management is more complicated than in the function context.

  • E.g. For a class that owns a dynamic int array:

    • Declare an instance variable int *array;

    • Allocation in the constructor or other methods this->array = new int[size];

    • Deallocation in the destructor, etc. delete[] this->array;

    • Deep copy in the copy constructor, copy assignment operator, etc.

      for (int i = 0; i < size; ++i)
  this->array[i] = other.array[i];

  • The ownership of the dynamic data is also more complicated. (FYI)

Memory Management in Class Context

  • Implicitly defined methods

  • Common mem problems in classes

  • The rule of three

  • Code example

    • shallow-copy.cpp: class with dynamic data and shallow copy

    • rule-of-3.cpp: improved version with the big three

Implicitly Defined Methods

  • The compiler will implicitly define the following methods if they are not explicitly defined by the programmer. They are called implicitly defined methods.

    • Default constructor: do nothing, potentially uninitialized variables

    • Copy constructor: straight copy by direct assignment, potentially shallow copy

    • Copy assignment operator overloading: straight copy by direct assignment, potentially shallow copy

    • Destructor: doing nothing

  • They can be used without explicitly defining them.

  • They will cause problem only when your class owns dynamic data and they are triggered.

    • You can totally rely on the implicit ones if your class does not own dynamic data.

    • You can explicitly define them to avoid the problems.

    • You can omit the ones that are not triggered even if your class owns dynamic data. Must be careful!

How to trigger

  • Default constructor

    • The constructor without any parameter

    • MyClass myObj();

    • MyClass *obj = new MyClass();

    • MyClass obj[10];

    • You can always omit () after the class name when they are empty.

  • Copy constructor

    • The constructor with one parameter of the same type as the class

    • MyClass myObj(otherObj); or MyClass myObj = otherObj;

    • MyClass *obj = new MyClass(otherObj);

    • Parameter passing by value void func(MyClass obj)

  • Copy assignment operator overloading

    • MyClass obj1, obj2(10); and then obj1 = obj2;

  • Destructor

    • When the local object is out of scope

    • MyClass *obj = new MyClass(); delete obj;

Common Memory Management Problems in Class Context

  • Memory leak

    • forget to deallocate the dynamic data in the destructor

  • Shallow copy

    • use a = operator to copy dynamic data

    • triggered the implicitly defined copy constructor and copy assignment operator with dynamic data

    • May cause double free

Solution: Explicitly Defining These Methods

  • Precondition: your class owns dynamic data

  • Default constructor: initialize the pointer to nullptr or allocate memory. Or stay away and always use other constructors

  • Copy constructor: deep copy the dynamic data

  • Copy assignment operator overloading: deep copy the dynamic data

  • Destructor: deallocate the dynamic data

  • Known as the “The Rule of Three”

The Rule of Three

  • The “Rule of Three”

    • The Big Three: destructor, copy constructor, copy assignment operator overloading

    • Although they may not all be triggered, it is safer to define them all explicitly.

  • The “Rule of Three” is a rule (not a law)

    • Not enforced by the compiler.

    • Rather a guideline for memory security.

  • The “Rule of five” after C++11 for performance optimization (FYI)

    • Move constructor

    • Move assignment operator overloading

Example Class with Dynamic Data

  • Code Example

  • Copy constructor:

    • Must take a const reference to class. Pass by value will trigger the copy constructor itself and cause problem.

  • Copy assignment operator overloading:

    • Must take a reference to the object too.

    • Must check self-assignment.

    • May need to deallocate the existing dynamic data before allocating new memory and copying the data.

    • Must return *this to allow chained assignment, if the return type is a reference to the class.

Ownership of the Dynamic Data (FYI)

  • Knowing who owns the dynamic data is important for memory management.

  • The class may:

    • Own the dynamic data.

      • implement the big three.

    • Own a pointer to the external dynamic data

      • treat the pointer as a regular variable

      • let the external owner to manage the dynamic data