RAII and Growable Containers
Participation
Loading...

Export your exercise answers to use with another computer or browser.

RAII and Growable Containers

Let's take a look at two common strategies for managing dynamic memory:

  1. RAII - The use of constructors and destructors to manage dynamic resources within a class-based ADT.

  2. Growable Containers - Dynamic memory enables a data structure to allocate additional space for elements as needed.

Updated Fall 2024
1: Warm Up Exercise
1.1 Not Started
1.1 Exercise: Warm Up

Let's review some of the issues we can run into with dynamic memory. What memory errors do you see in the code below?

int *func(int x) {
  int *y = new int(x);
  y = new int[x];
  return y;
}

int main() {
  int *a = func(5);
  int *b = a;
  delete b;
  cout << a[2] << endl;
}

Describe a few conceptual problems and/or specific errors in the way the code above manages dynamic memory.

You're welcome to check your solution with this walkthrough video:

2: RAII: A Strategy for Managing Dynamic Resources
2.1 Not Started

We've seen a few strategies for managing dynamic memory so far. Let's consider one more, which is to use constructors and destructors for a class to manage the allocation and deletion of dynamically allocated memory.

This strategy is often called "Resource Acquisition Is Initialization (RAII)". Here's some motivation and the details:


To recap, the strategy is essentially:

  • Allocate dynamic resources in a constructor, as part of initializing a class object.
  • Track the dynamic memory using a pointer stored as a private member variable, provide access as desired through public member functions.
  • When the class object dies (e.g. goes out of scope), its destructor ensures the dynamically allocated resources are properly deleted.
2.1 Exercise: RAII and Memory Management

Which of these functions leak memory? Write either "ok" or "memory leak", as well as a brief justification. You should assume the constructors and destructor for UnsortedSet are defined (correctly) as described above for DynamicIntArray, such that the constructor and destructor take care of creating and destroying the internal array used to store set elements.

void func() {
  UnsortedSet<int> s1;
  s1.insert(2);
  s1.insert(3);
}

void func() {
  UnsortedSet<int*> s2;
  s2.insert(new int(2));
  s2.insert(new int(3));
}

void func() {
  UnsortedSet<int> *s3 = new UnsortedSet<int>;
  s3->insert(2);
  s3->insert(3);
}

void func() {
  UnsortedSet<int> *s4 = new UnsortedSet<int>;
  s4->insert(2);
  s4->insert(3);
  delete s4;
}

You're welcome to check your solution with this walkthrough video:

3: Growable Containers
3.1 Not Started

Previously, we implemented containers with a fixed-capacity restriction. Using dynamic memory, we can instead implement growable containers that start with a small amount of dynamic memory and allocate more as needed.


3.1 Exercise: UnsortedIntSet::grow()

Fill in the code for the grow() function for UnsortedIntSet using the algorithm described in the video (it is also repeated in the comments above the function in the code below).

The main() function provided includes testing code to verify your implementation.

You're welcome to check your solution with this walkthrough video:

Note that the walkthrough is for a templated class with type T whereas the exercise used int specifically. The concept is the same otherwise.

4: Dynamic Resource Invariants

Let's take just a moment to formally reason about the management of dynamic resources by an ADT and sketch out a rough strategy for proving they don't leak memory or run into other memory errors.
You've reached the end of this lecture! Your work on any exercises will be saved if you re-open this page in the same web browser.

Participation Credit
Make sure to sign in to the page, complete each of the exercises, and double check the participation indicator at the top left of this page to ensure you've earned credit.