Announcements

Just a few notes before we start today's section:

...starting with candy! I grant unto you more of my inexhaustible Halloween reserve in an effort to thank you for filling out the study survey, completing my evaluations, and to keep you bribed energized with sugar for class.

Sooo Saturday Final everybody! Make sure you know which room you're in as follows:

From 11:30 AM to 2:00 PM in Dodd 147 if your last name begins with: B, D, F, G, H, I, J, O, P, Q, R, T, V, X, or Y
From 11:40 AM to 2:10 PM in Dodd 121 if your last name begins with: S, N, A, K, or E
From 11:50 AM to 2:20 PM in Humanities A51 if your last name begins with: C, L, M, W, or Z

You are allowed TWO, count them, TWO cheat sheets for the final... double sided! That's a lot of notes!

I will be conducting a last-minute Question & Answer section on Saturday from 10:15 - 11:15 am in Rolfe 1200 in an effort to quell your panic!

Dynamic Memory

Just when you thought you could forget about memory (fact: that pun is inexaustible), we start talking about dynamic memory...

So what's the big deal about this new craze called dynamic memory?

Well, let's think about the memory we've been using in the recent past...

When we wanted to create an array of ints, do we always have to somehow specify its size? Could this be done at runtime?

In our experience, we needed to specify the size of an array; sometimes this could be inferred via syntax: int i[] = {1, 2, 3}; but size allocations like the following could not be done at runtime:

  ...
  int count;
  cin >> count;
  
  // Would this be legal?
  int i[count];
  ...

But Andrew... does that mean we are forever bound to specifying our memory allocations at runtime?

Will we ever be free of these shackles?

Fear not, for now we turn to Dynamic Memory.

Dynamic Memory Allocation is the runtime-capable allocation of memory that is managed by the programmer. It is used for allocating some amount of memory not necessarily known at compile time.

We should discuss a couple of topics to see the big difference between dynamic memory and local allocations.

For starters, the memory location in which we've previously been storing variables is called the stack.

The stack, more formally known as the call stack, pushes local variables onto its top as they are declared, and then "pops" them from the top when they fall out of scope.

The big difference between this act of "popping" a variable from memory is done automatically with scope when variables are stored in the stack, but is NOT done without programmer intervention with dynamic memory.

So if dynamic variables aren't kept in the stack like with our previously experienced variables, where are they kept?

The heap, by contrast, is where dynamic memory is allocated, and does not operate in the same "stacked" fashion that the... well... stack does.

So let's just review some key differences between the two:

	Stack	Heap
What variables live here?	Local variables, functions, function arguments, etc.	Dynamically allocated memory reserved by the programmer
How can variables be accessed?	By any type of identifier defined in scope	Only through pointers!
Best for storing:	Local variables that are specific to limited scopes	Variables whose size is not known at compile-time
Memory is allocated:	Whenever a variable is declared in scope	Whenever the `new` keyword is used to initialize a variable and call a constructor
Memory is freed / deallocated:	Whenever a variable disappears from scope (e.g., local variables in a function after returning from that function)	Only after the delete keyword is used!

So in brief: dynamic memory gives us the luxury of allocating memory on-the-fly during runtime, but at the cost of some performance and the necessity to keep track of deallocating memory ourselves.

So why do we need to deallocate the memory we've dynamically reserved?

Well, we allocated it on our own so we must also deallocate it on our own, or else the compiler won't know if it's still needed or not!

Now that we have the background in place, let's take a look at the specifics of using dynamic memory in C++:

Memory Allocation Syntax

To dynamically allocate memory for a given object, we use the new keyword. The new keyword invokes a constructor for a given object based on that constructor's expected parameters:

  // For any number of expected constructor
  // parameters (including none)
  <type>* <name> = new <type>(parameter1, parameter2, ...);

Why not some examples?

  #include <iostream>
  #include <string>
  #include <cstring>
  using namespace std;
  
  struct dullExample {
      int i;
      string s;
  
      // Default constructor
      dullExample () {
          i = 5;
          s = "wow!";
      }
  
      // Constructor 2
      dullExample (int j, string str) {
          i = j;
          s = str;
      }
  };
  
  int main () {
      // Note two things:
        // laaame is a POINTER
        // We're calling the default constructor here
      dullExample* laaame = new dullExample();
      cout << laaame->i << endl;
      cout << laaame->s << endl;
  
      // HERE, we're using constructor 2 in our dynamic allocation
      dullExample* uuugh = new dullExample(3, ":(");
      cout << uuugh->i << endl;
      cout << uuugh->s << endl;
  
      // WARNING: We should deallocate the memory here so as not to have
      // a leak, but we haven't learned how to do that yet...
  }

You should know that, although it's often rather silly in most cases to do so, we can even dynamically allocate memory for primitive types:

  // Stick i in the heap and initialize it to 2
  int* i = new int(2);
  cout << *i << endl;
  
  // Of course, would need to deallocate here still... derp

Using the struct definition from above, will the following code compile? Also, is bore on the stack or heap?

  int main () {
      dullExample bore(5, ">_> <_<");
      cout << bore.i << endl;
      cout << bore.s << endl;
  
      // Also, do we need to deallocate bore here?
  }

Will the following code compile? If so, what will it print out?

  int main () {
      dullExample dynamic = new dullExample();
      dullExample duo = dynamic;
  
      cout << dynamic.i << endl;
      cout << duo.i << endl;
      
      // TODO: What needs to be de-allocated here?
  }

Will the following code compile? If so, what will it print out?

  int main () {
      dullExample* dynamic = new dullExample();
      dullExample* duo = dynamic;
  
      cout << dynamic->i << endl;
      duo->i = 5;
      cout << dynamic->i << endl;
      
      // TODO: What needs to be deallocated here?
  }

Dynamic Memory can even be used to specify arrays of variable size at runtime!

  #include <iostream>
  #include <string>
  #include <cstring>
  using namespace std;
  
  struct inStructive {
      inStructive() {
          i = 5;
      }
  
      double d;
      int i;
      char c;
  };
  
  int main () {
      int count;
      cout << "Enter the size:" << endl;
      cin >> count;
  
      int* i = new int[count];
  
      for (int j = 0; j < count; j++) {
          i[j] = j;
          cout << i[j] << endl;
      }
      
      // Will need to see how to prevent a memory leak here...
      // i.e., how to delete arrays of objects... stay tuned!
  }

Say we had a class called A with a member that was a 1,000,000 element array, and we needed to make an array of these objects that is *at most* 10,000 elements long. Would you prefer to use a local variable or dynamic allocation for this array, and what type should the elements of this array be?

Because these A objects take up a lot of space, we might consider making our array an array of Pointers to A objects, such that we don't start off with all 10,000 A objects constructed with their 1,000,000 element array members each, but instead have the capacity to be later allocated so we don't waste space.

Alright, grand... so let's look at the messy part... deallocating memory.

Memory Deallocation Syntax

Rule of thumb: whenever we dynamically allocate memory using the new keyword, we must later release it using the delete keyword.

If we fail to do so, we get a memory leak:

A memory leak is defined as a failure in a program to release discarded memory, causing impaired performance or failure.

Memory leaks become problems when we repeatedly forget to free dynamically allocated memory, and we have large, discarded objects that are still allocated but can no longer be reached.

These memory leaks add up until our code may not have enough dynamic memory left to allocate, or doing so slows it substantially.

Here are some properties of the delete keyword:

delete effectively says, "I'm done with this object's dynamically allocated memory; feel free to do with it what you please!" We call delete on the pointer to said object.
NOTE: This does NOT say, "Zero out the memory it was pointing to" nor does it say "Set the pointer that was pointing there to NULL or nullptr."
delete called on an object that was already deleted is undefined behavior!
delete called on a nullptr is fine, and does nothing.
delete only NEEDS to be called on objects that were initialized using the new operator.

There are two separate forms of delete used as follows:

  delete <name_Of_SINGLE_Object>;
  delete[] <name_Of_ARRAY_Of_Objects>;

In the first case, delete only frees the memory of a single object. Here's an example from earlier:

  #include <iostream>
  #include <string>
  #include <cstring>
  using namespace std;
  
  struct dullExample {
      int i;
      string s;
  
      // Default constructor
      dullExample () {
          i = 5;
          s = "wow!";
      }
  
      // Constructor 2
      dullExample (int j, string str) {
          i = j;
          s = str;
      }
  };
  
  int main () {
      dullExample* laaame = new dullExample();
      cout << laaame->i << endl;
      cout << laaame->s << endl;

      dullExample* uuugh = new dullExample(3, ":(");
      cout << uuugh->i << endl;
      cout << uuugh->s << endl;
  
      // Be free memory! Be free!
      delete laaame;
      delete uuugh;
  }

Where will laaame and uuugh point after we call delete on them above?

Exactly where they were beforehand! That is, they'll point to the same memory address as they did before, but that memory will now be deallocated.

The second version of delete, delete[], says, "Release the memory for this array, and call the destructor of every element for it, if it exists." (We'll talk about destructors momentarily).

NOTE: You only need to use delete[] if you have used new[] to dynamically allocate an array of objects.

This is beyond the scope of CS31, so we'll wave our hands over it now... see you in CS32 for more on that discussion.

Shall we look at some examples?

Find the memory leak!

  #include <iostream>
  #include <string>
  #include <cstring>
  using namespace std;
  
  struct dullExample {
      int i;
      string s;
  
      // Default constructor
      dullExample () {
          i = 5;
          s = "wow!";
      }
  
      // Constructor 2
      dullExample (int j, string str) {
          i = j;
          s = str;
      }
  };
  
  int main () {
      dullExample* onion[5];
      
      for (int i = 0; i < 5; i++) {
          onion[i] = new dullExample(i, "get it? onion leek?");
          // Aren't you glad this is the last day?
      }

      // Done! :DDDDD
      delete onion;
  }

Find the memory leak!

  #include <iostream>
  #include <string>
  #include <cstring>
  using namespace std;
  
  struct superDull {
      int lame;
      double doubleLame;
  
      superDull () {
          lame = -100;
      }
  };
  
  struct dullExample {
      int i;
      string s;
      // or is it evenMoreDull?
      superDull* evenDuller;
  
      dullExample () {
          i = 5;
          s = "wow!";
          evenDuller = new superDull();
      }
  };
    
  int main () {
      dullExample* faucet = new dullExample();
      cout << faucet->evenDuller->lame << endl;
  
      // Done... :|
      delete faucet;
  }

Will the following code compile? If so, what will it print out?

  #include <iostream>
  #include <string>
  #include <cstring>
  using namespace std;
  
  struct dullExample {
      int i;
      string s;
  
      dullExample () {
          i = 5;
          s = "wow!";
      }
  };
    
  int main () {
      dullExample dullAgain;
      cout << dullAgain.i << endl;
  
      delete dullAgain;
  }

Will the following code compile? If so, will it experience any undefined behavior?

  #include <iostream>
  #include <string>
  #include <cstring>
  using namespace std;
  
  struct dullExample {
      int i;
      string s;
  
      dullExample () {
          i = 5;
          s = "wow!";
      }
  };
    
  int main () {
      dullExample* dullAgain = new dullExample();
      dullExample* dittoDull = dullAgain;
      
      delete dullAgain;
      delete dittoDull;
      cout << (dullAgain == dittoDull) << endl;
  }

Assuming we removed one of the two delete statements in the above example, what would the program print out?

1 (true) because although we've deallocated the memory that the two pointers point to, they still point to the same spot!

More on Structs

...because I didn't say enough about structs last week... or this week for that matter...

Mostly, we need to talk about some special member functions. Let's start by adding some details about the constructor.

We can define multiple constructors for a given type as long as we follow certain rules. Starting with the basics:

The Default Constructor is the constructor that expects no arguments.

There are some special properties about the default constructor:

If you do not specify one, the compiler will generate one for you... this generated default will initialize NO primitive members, but will call the default constructors of all other object members.
You cannot define more than one default constructor
If YOU do not define a default constructor, but instead define another constructor (expecting some number of arguments), the compiler will no longer generate one for you.

Returning to our running example, we see the default constructor:

  struct dullExample {
      int i;
      string s;
      
      // Default constructor
      dullExample () {
          i = 5;
          s = "wow!";
      }
  };

Will the following code compile?

  #include <iostream>
  #include <string>
  #include <cstring>
  using namespace std;
  
  struct dullExample {
      int i;
      string s;
  
      dullExample (int j, string s) {
          i = 5;
          s = "wow!";
      }
  };
    
  int main () {
      dullExample* oopsies = new dullExample();
  
      cout << oopsies->i << endl;
      cout << oopsies->s << endl;
  
      delete oopsies;
  }

In fact, this last rule is a special case of a more general one:

WARNING: You cannot have two constructors that expect the same number and type of arguments in the same order.

For example, the following is OK because the parameters, although the same type between constructors, are in a different order.

  struct dullExample {
      int i;
      string s;
  
      dullExample (int j, string str) {
          i = j;
          s = str;
      }
  
      dullExample (string str, int j) {
          i = j;
          s = str;
      }
  };

But the following is NOT OK:

  struct dullExample {
      int i;
      string s;
  
      dullExample (int j, string str) {
          i = j;
          s = str;
      }
  
      dullExample (int stuff, string derp) {
          i = stuff;
          s = derp;
      }
  };

OK that's enough constructor trivia for now... let's address the following scenario:

Say I had a struct with a bunch of dynamically allocated members...

What would I need to do before I deallocated an instance of that object?

I would have to individually deallocate each of the dynamically allocated members! Nobody got time for that!

Enter destructors, which are special functions defined on a struct / class that are called whenever (1) that object was locally defined and fell out of scope, or (2) that object was dynamically defined and had a form of delete called upon it.

Destructors use the following syntax:

  struct someStruct {
    ...
    // Constructor
    someStruct (...) {
      ...
    }
    
    // Destructor
    ~someStruct () {
      ...
    }
  };

Notice that the destructor syntax has the following properties:

Shares the same name of the struct / class
Starts with a tilde (~)
Has no return type
Expects no arguments

So let's look at some correct destructor definitions and uses:

  #include <iostream>
  #include <string>
  #include <cstring>
  using namespace std;
  
  struct SuperInterestingMember {
      string actuallyNotThatInteresting;
  
      SuperInterestingMember () {
          actuallyNotThatInteresting = "Meh...";
      }
  };
  
  struct SuperInterestingExample {
      int i;
      string s;
      SuperInterestingMember* ob;
  
      // Constructor dynamically allocates member
      // ob of type SuperInterestingMember
      SuperInterestingExample () {
          i = 5;
          s = "wow that's interesting!";
          ob = new SuperInterestingMember();
      }
  
      // DESTRUCTOOOOOOR
      ~SuperInterestingExample () {
          cout << "[!] Destructor called!" << endl;
          delete ob;
      }
  };
  
  // [!] What gets printed in the main function and in what order?
  int main () {
      // NOTICE: sup is not a pointer, just an object declaration
      SuperInterestingExample sup;
    
      cout << sup.ob->actuallyNotThatInteresting << endl;
  }

Now, what if we had a dynamic allocation?

  #include <iostream>
  #include <string>
  #include <cstring>
  using namespace std;
  
  struct SuperInterestingMember {
      string actuallyNotThatInteresting;
  
      SuperInterestingMember () {
          actuallyNotThatInteresting = "Meh...";
      }
  };
  
  struct SuperInterestingExample {
      int i;
      string s;
      SuperInterestingMember* ob;
  
      SuperInterestingExample () {
          i = 5;
          s = "wow that's interesting!";
          ob = new SuperInterestingMember();
      }
  
      // DESTRUCTOOOOOOR
      ~SuperInterestingExample () {
          cout << "[!] Destructor called!" << endl;
          delete ob;
      }
  
  };
  
  // [!] What gets printed in the main function and in what order?
  int main () {
      // NOTICE: sup is now a dynamically allocated var
      SuperInterestingExample* sup = new SuperInterestingExample();
    
      cout << sup->ob->actuallyNotThatInteresting << endl;
    
      // Destructor will get called here so I
      // don't have to worry about releasing ob
      delete sup;
      
      cout << "Just at the end of main here... nothing to see!" << endl;
  }

How nice that is!

Alright, let's look at some crumby examples when some fools tried to use destructors:

Will the following code compile? If so, will it suffer any undefined behavior? Will it print something?

  #include <iostream>
  #include <string>
  #include <cstring>
  using namespace std;
  
  struct SuperInterestingMember {
      string actuallyNotThatInteresting;
  
      SuperInterestingMember () {
          actuallyNotThatInteresting = "Meh...";
      }
  };
  
  struct SuperInterestingExample {
      int i;
      string s;
      SuperInterestingMember* ob;
  
      // NOTICE: change in the constructor...
      SuperInterestingExample () {
          i = 5;
          s = "wow that's interesting!";
      }
  
      ~SuperInterestingExample () {
          delete ob;
      }
  
  };
  
  int main () {
      SuperInterestingExample* sup = new SuperInterestingExample();
    
      cout << sup->ob->actuallyNotThatInteresting << endl;
    
      delete sup;
  }

So how can we avoid this issue of not initializing a member object (maybe we don't want to until we need it) and having our destructor try to clean it up?

Initialize it to the nullptr in the constructor!

Practice

Let's go through some examples that might just be tricky enough to make the final...

There's a rather insidious bug in this piece of code that will cause it to crash... where is it and why?

  #include <iostream>
  #include <string>
  #include <cstring>
  using namespace std;
    
  struct dullExample {
      int i;
      string s;
      
      // or is it "evenMoreDull"?
      dullExample* evenDuller;
      
      dullExample () {
          i = 5;
          s = "wow!";
          evenDuller = new dullExample();
      }
  };
  
  int main () {
      dullExample* faucet = new dullExample();
      cout << faucet->evenDuller->i << endl;
      
      // Done... :|
      delete faucet;
  }

Find the memory leak!

  #include <iostream>
  #include <string>
  #include <cstring>
  using namespace std;
  
  struct SuperInterestingMember {
      string actuallyNotThatInteresting;
  
      SuperInterestingMember () {
          actuallyNotThatInteresting = "Meh...";
      }
  };
  
  struct SuperInterestingExample {
      int i;
      string s;
      SuperInterestingMember* ob;
  
      // NOTICE: change in the constructor...
      SuperInterestingExample () {
          i = 5;
          s = "wow that's interesting!";
          ob = new SuperInterestingMember();
      }
  
      ~SuperInterestingExample () {
          delete ob;
      }
  
  };
  
  int main () {
      SuperInterestingExample* sup = new SuperInterestingExample();
    
      cout << sup->ob->actuallyNotThatInteresting << endl;
  }

Find the memory leak!

  #include <iostream>
  #include <string>
  #include <cstring>
  using namespace std;
  
  struct superOb {
      int i[3];
  
      superOb () {
          for (int j = 0; j < 3; j++) {
              i[j] = j;
          }
      }
  };
  
  struct superEx {
      int i;
      string s;
      superOb* ob;
  
      superEx () {
          i = 5;
          s = "wow that's interesting!";
          ob = new superOb();
      }
  
      ~superEx () {
          delete ob;
      }
  };
  
  superEx* generateCoolness () {
      superEx* coolness = new superEx();
      return coolness;
  }
  
  int main () {
      superEx* sup = generateCoolness();
    
      for (int j = 0; j < 3; j++) {
          cout << sup->ob->i[j] << endl;
      }
  }

Will the following code compile? Will there be any undefined behavior? Will it print anything out?

  #include <iostream>
  #include <string>
  #include <cstring>
  using namespace std;
  
  struct superOb {
      string s;
  
      superOb () {
          string s = "watch out!";
      }
  };
  
  struct superEx {
      int i;
      string s;
      superOb* ob;
  
      superEx () {
          i = 5;
          s = "wow that's interesting!";
          ob = new superOb();
      }
  
      ~superEx () {
          delete ob;
      }
  };
  
  int main () {
      superEx* sup = new superEx();
  
      cout << sup->ob->s << endl;
  
      delete sup->ob;
      delete sup;
  }

Find the memory leak!

  #include <iostream>
  #include <string>
  #include <cstring>
  using namespace std;
  
  const int MAX_INTS = 3;
  
  struct FinalBoss {
      int* i[MAX_INTS];
    
      FinalBoss () {
          for (int j = 0; j < MAX_INTS; j++) {
              i[j] = new int(j);
          }
      }
    
      ~FinalBoss () {
          delete i;
      }
  };
    
  int main () {
      FinalBoss* bowserdorf = new FinalBoss();
    
      cout << bowserdorf->i[0] << endl;
    
      delete bowserdorf;
  }

Good Luck!

Just a parting word of encouragement for your final!

It's been an honor and privilege to be your TA throughout the quarter; I know personally that you shall crush your exams!

If you could do me one last solid, I would truly appreciate any feedback on the course through your TA evaluations. I genuinely enjoy teaching and want to make these the best lectures possible, so please let me know what you would change for next time and what I actually did right!

Say hi next time you're in the TA office hours room!