More pointers, dynamic memory

Review of last time

References: references are just another name for an existing box:

int a = 1;
int& b = a; // Now b is another name for a's box

Pointers: pointers are like references that can change what they refer to while the program is running:

int a = 1, b = 2;
int* c = &a; // c points to a
*c = 3;      // Now a = 3
c = &b;      // c points to b
*c = 12;     // Now b = 12

References are interesting when we use them as the arguments to functions.

We can create references and pointers to anything that has its own box. This includes elements of arrays, vectors and strings.

We can create pointers to pointers:

int a = 1;
int* b = &a; // b points to a
int** c = &b; // c points to b

An example: Let’s write a function which takes two pointers and returns a pointer to the smallest pointed-to value:

int* min(int *a, int *b) {
  if(*a < *b) {
    return a;
  }
  else
    return b;
}

// Using the conditional operator:
int* min(int* a, int *b) {
  return *a < *b ? a : b;
}

Another example: Let’s write a function which searches a vector for a given value. If it exists, we return a pointer to it. If it does not, we return nullptr:

int* find(vector<int> data, int target) {
  for(int i = 0; i < data.size(); i++)
    if(data.at(i) == target)
      return &(data.at(i));

  return nullptr;
}

Can we use a ranged-for loop for this? Yes, provided we remember to use a reference:

int* find(vector<int> data, int target) {
  for(int& e : data) 
    if(e == target)
      return &e;

  return nullptr;
}

What happens if we leave off the reference on the loop variable? Then it’s the same as if we had written

int* find(vector<int> data, int target) {
  for(int i = 0; i < data.size(); i++) {
    int e = data.at(i);
    if(e == target)
      return &e;
  }

  return nullptr;
}

Here we’re returning a pointer to e, but e has no connection with data, it’s an independent variable. The address of e is basically worthless, because it goes away after the loop.

If we create e as a reference to the elements of the vector, then getting the address of e is the same as getting the address of data.at(i) for some i.

Pointers to functions

In addition to pointers to values (and pointers-to-pointers, etc.) we can create pointers to functions. This allows us to call a function, without knowing exactly which function will be called!

Here’s an example:

int add(int a, int b) {
  return a + b;
}

int subtract(int a, int b) {
  return a - b;
}

int main() {
  cout << "Enter two numbers: ";
  int a,b;
  cin >> a >> b;

  cout << "Do you want to add or subtract (a/s)? ";
  char choice;
  cin >> choice;

  int (*operation)(int,int) = (choice == 'a' ? &add : &subtract);

  cout << "The result is " << operation(a,b) << endl;
  return 0;
}

The line int (*operation)(int,int) creates a pointer-to-function named operation. The functions that it may point to must return an int, and must take two ints as parameters. We use a conditional operator to initialize it to either add or sub. Note that for functions, &add is equivalent to add by itself, so we could simplify this line to

int (*operation)(int,int) = (choice == 'a' ? add : sub);

To use a function pointer, just pretend that it’s a function and call it normally:

cout << "The result is " << operation(a,b) << endl;

Depending on the user’s input, operation will either point to add or sub, which determines which operation will be performed.

Function pointers can be combined with arrays and vectors, to create collections of related operations, provided they all have the same signatures (return type and argument types):

vector<int(*)(int,int)> functions;
functions.push_back(add);
functions.push_back(subtract);

(functions.at(0))(1,2); // returns 3
(functions.at(1))(1,2); // returns -1

(The type int(*)(int,int) is the type of “pointers to functions that return an int and take two int arguments”.)

Similarly, we can write a function which takes a function pointer:

int square(int x) {
  return x * x;
}

int run_twice(int x, int(*f)(int) ) {
  return f(f(x)); 
}
...
run_twice(2, square) // evaluates to (2*2) * (2*2) = 16

This is yet another way of abstraction out a facet of a functions operation: you can let the user “plug in” some details by providing function pointers.

An Example

As an example of how function pointers can be useful, let’s write a function that can be used to perform the same effect as almost any accumulating loop. Remember that for an accumulating loop we need two things:

Assuming we have a vector of ints, and that the type of x is also int, then the type of OP is int(*)(int,int); i.e., it’s a function pointer that takes two ints, and returns an int. Our function now looks like this

int accumulate(vector<int> data, 
               int identity, 
               int(*operation)(int,int)) {

  int a = identity;
  for(int e : data)
    a = operation(a,e);

  return e;
}

If we do

int x = accumulate(data, 0, add);

I’ll get the sum. If we do

int multiply(int x, int y) { return x*y; }

accumulate(data, 1, multiply);

I’ll get the product.

We can even make a version that finds the smallest (or largest). In this case, the operation is min, a function that returns the smaller of its two inputs:

// Note: this function is already defined in #include<utility>
int min(int a, int b) {
    return a < b ? a : b;
}

accumulate(data, data.at(0), min) // returns the smallest element

Another example:

Dynamic memory

One of the major restrictions on arrays is that they must have a size that is fixed when your program is created. E.g., you cannot do something like this:

int n; 
cin >> n;

int arr[n]; // Create an array of size n; THIS DOES NOT WORK

This raises the question of how things like string and vector can possibly work? They aren’t magic; string and vector were both written, in C++, by somebody, so there must be some way to store a variable amount of “stuff”.

Put another way, without string and vector, there is an exactly one-to-one correspondence between the number of variables in our program, and how values we can store. If you want to store 10 char values (without string), then you’d need 10 char variables, or a char array of size 10. If you don’t know how many chars you need (as is the case with a string which can shrink and grow while a program is running), how can we do this?

While the number of variables in our program is fixed when we write it (you could go through and count exactly how many char variables you have), we can request “unnamed” values, at runtime. The values have to be unnamed (not linked to variables) because we don’t know how many we’ll need until the program is running. But if a value is unnamed, how can we manipulate it? We have to use the only tool we have for talking about things without using their names directly: pointers.

Here we’re going to see how we can create space for both single objects and arrays at runtime, with a dynamic size like n, above.

To create an object at runtime, we use new:

int* i = new int();       // returns an int*
char* c = new char();     // returns a char*
string* s = new string(); // returns a string*

new creates a new value of the type requested, and returns a pointer to it. It returns a pointer, because the new value is not attached to any particular name; no variable “owns” it.

You might wonder what the difference is between doing

string s;

and doing 

string* s = new string();

and the difference has to do with lifetime.

Scope and lifetime

Scope is the region of your program where a given variable is accessible. It is part of your program from the start; you don’t need to run your program in order to find out the scope of something, you can just look at it. We call a property like this, that you can determine just by looking at the source code, a static property.

There is an analogous property for values that is called lifetime. The lifetime of a value is how long, at run time, will that value continue to exist. (Properties like this, that can be determined in the last resort, only by running the program, are called dynamic properties.)

Normally, the lifetime of a value is tied to the scope of the variable that contains it. When we write:

void f() {
    string s;
    ...
}

The string inside s has a lifetime that begins when f starts, and ends when f returns. That is, it’s basically the same as the scope of s.

When I create a value with new, it has potentially unlimited lifetime:

void f() {
    string* s = new string();
    ...
}

The string pointed to by s does not go away when f returns. It lives on. It is no longer accessible (because s, the only way to access it, went out of scope), but it still exists, and it still takes up memory. If we had preserved the pointer to it in s, we could continue to use it after f returned.

Another way to think of this is that new creates an unnamed box. Because it has no name, we can conclude two things about it:

How long is the lifetime of objects created with new? Well, in the last resort, all objects die when your program quits. So theoretically, until the end of your program. But this is usually not what we want, so instead, we can say when an object’s lifetime should end ourselves:

delete s;

If new creates a free-floating object, delete destroys one. After delete s;, the pointer s is no longer valid. In fact, it’s good practice to set a pointer to null when you delete it:

delete s;
s = nullptr;

The stack and the heap

To understand why things created via new have a different lifetime, we need to talk about the two parts of memory that our programs can use: the stack and the heap.

When we write a function (including main) that declares some variables, where in memory do those variables exist? They exist on the stack. The stack works like this:

Thus, the stack forms a literal stack: you put things on top and they cover up the things below them, but when you remove the top thing, you get access to whatever was originally below it. This is how functions keep track of who called who, and what the different functions were originally doing.

E.g., suppose we have these functions:

int main() {
  int x; 

  f();
  g();
  h();
}

void f() {
  int y;

  h();
  g();
}

void g() {
  int z;
  h();
}

void h() {
  int x;
}

(Run through this).

When a function returns a value (not a reference) it must make a copy:

void f() {
  int y = g();
}

int g() {
  int x = 12;
  return x;
}

The value in x is copied into the record for f as part of the return process. This is why we can return a reference to a variable within g, because the record containing that variable will have disappeared after the return is complete.

The stack is nice because it cleans up after us, we don’t have to worry about manually deleting variables when we’re done with them. But if we want more control over the lifetime of the values, we can’t use the stack, because it handles lifetimes automatically. If I want to create an object in one function, return it (not a copy of it), and then release it in a different function, the stack won’t work for that. So there’s another region of memory, for manually-managed objects: the heap.

The heap is just a big chunk of memory dedicated to your program. When you do new string new goes out and finds some unused portion of it big enough to store a string, and reserves it, and then gives you back a pointer to that part of memory. Because it’s not on the stack, that memory is not affected by the normal function call-return process; it lives until you tell it to go away. Which you do by delete-ing it. delete-ing a piece of the heap just tells the system to make it as unused again, so that it’s free to be used to satisfy another new later on. (Note that you cannot delete stack-based variables, don’t even try, or terrible things will happen.)

This also explains why new and delete only work with pointers. Only variables that are on the stack have names. The heap has no names, just chunks of memory that have been reserved for various purposes. The only way to access such a piece of memory is thus through a pointer.

There isn’t much point (right now) in creating single values stored on the heap, usually we use it for arrays, but let’s do an example, to illustrate both how to use this memory, and how to use pointers to manipulate objects. This program prompts the user to enter their name (first and last), and then prints it out as first-initial last name. E.g., if you enter “Susan Smith” it will print “S. Smith”. 

int main() {
  string* name = get_name();

  cout << first_initial(name) << ". " 
       << last_name(name) << endl;

  delete name;
  return 0;
}

char first_initial(string* name) {
  return (*name).at(0); 
  // can be shortened to name->at(0);
}

string last_name(string *name) {
  int begin = (*name).find(" ") + 1;
  return (*name).substr(begin, (*name).length() - begin);
}

Why does last_name return a string and not a string*? Partly because that’s what substr returns. Let’s see what we have to do in order to make it return a string*:

string* last_name(string *name) {
  int begin = (*name).find(" ") + 1;

  // Create a string on the heap
  string* last = new string;

  // *Copy* the substring containing the last name into it
  *last = substr(begin, (*name).length() - begin);

  return last;
}

(Writing (*name).length() and such is so cumbersome that there’s a shorthand for doing this: name->length(). Whenever I might write (*thing).whatever I can write thing->whatever instead.)

But now we have to go and fix main: cout doesn’t know how to print a string*, it only knows how to work with string. So we have to do

int main() {
  string* name = get_name();

  string* last = last_name(name);

  cout << first_initial(name) << ". " << *last << endl;

  delete name;
  return 0;
}

What’s wrong with this code? I forgot to delete last! This illustrates some of the pitfalls of working with new memory and pointers: most of the tools we have aren’t setup for working with them, they’re more of a low-level detail that is normally hidden. You also have to be very careful to delete things that you create. Normally, that responsibility is hidden from us (e.g., string and vector use new and delete internally, but they handle calling delete when necessary); if we’re going to use heap-allocated memory, then suddenly we have the responsibility of cleaning up after ourselves.

Dynamically creating arrays

To create an array using new, we write this:

int* data = new int[10](); // Create an int array of size 10.

Once created, you can access the elements of it the same way as for a normal array:

data[0] = 1;

The interesting bit is that we do not have to use a constant like 10, we can just as well use a runtime value:

int main() {
  cout << "How many values are you going to enter? ";
  int size;
  cin >> size;

  int* data = new int[size]();

  // Read in data
  for(int i = 0; i < size; i++)
    cin >> data[i];

  // do stuff

  // Release the data
  delete[] data;

  return 0;
}

The line before the final return illustrates that there is a different syntax for deleting an array, vs. a single value. To delete an array you must use

delete[] arr;

The square brackets after delete tell the system that it is an array you are deleting. If you forget them, your program may crash in bizarre ways (e.g., it might crash later, after the delete, in some unrelated part of your program!).

Note that the two other restrictions on array still apply to these:

The size restriction is particularlly irksome, because it means that if we want to write a function that operates on a dynamic array, we have to include the size as another parameter:

int sum(int* data) {
  for(int i = 0; i < ???) // no way to find out the size!
}

int sum(int* data, int size) {
  int s = 0;
  for(int i = 0; i < size; i++)
    s += data[i];
}

Quiz: how do I write a pointer-based loop for the above?

int sum(int *data, int size) {
  int s = 0;
  for(int* p = &data[0]; p != &data[size]; p++)
    s += *p;
}

Note that with a dynamically allocated array, you cannot use a range-based for loop. A normal, statically created array has its size “hidden” somewhere with it, so that the range-based for knows when to stop. A pointer is just a pointer; it has no size information (this is also why we have to remember to use delete[] instead of delete, because the system doesn’t know whether a pointer is to an array, or to a single object).

Array to pointer conversion

A statically-allocated array is a different kind of thing from a pointer to a dynamically-allocated array, but we can convert the former into the latter. (Note that this loses the hidden size information!) Basically, a static array of (say) int can be implicitly converted to an int*:

int data[] = {1, 2, 3, 4, 5};

int x = sum(data, 5);

The array data, when converted to an int*, converts to a pointer to data[0]. In otherwords, the above is exactly equivalent to

int data[] = {1, 2, 3, 4, 5};

int x = sum(&data[0], 5);

This means that any functions we write that work with arrays created via new can also be used with static arrays, transparently.

This also gives us a new way to write arr[x]:

int arr[] = {1, 2, 3, 4, 5, 6};

int* p = arr; // points to arr[0]

*(p + 2) // accesses p[2]

p[2] // also accesses p[2]

Advancing a pointer by x and then accessing it is exactly the same as writing p[x]; the second is just a shorthand for the first.

Examples

Using arrays created via new and delete is basically like using standard arrays, you just have to remember to free them after you’re done.

Reading in some numbers from the user:

int* read_numbers() {
  cout << "How many numbers are you going to enter? ";
  int n; 
  cin >> n;

  int* data = new int[n]();

  cout << "Enter numbers: ";
  int i = 0;
  while(i < n) {
    cin >> data[i];
    i++;
  }

  return data;
}

Note that this illustrates an important point: a function can create an array via new and then return it, and it’s the responsibility of the calling function to free it when it’s done. E.g., our main might look something like

int main() {
  int* nums = read_numbers(); 

  // Do something with nums

  delete[] nums;
  return 0;
}

Checking whether an array contains a number:

int* find(int* data, int size, int value) {
  for(int *p = data; p != data + size; p++) {
    if(*p == value)
      return p;
  }
  return nullptr;
}

This function returns either a pointer to the element containing value in the array, or nullptr if it is not found. If we want to know the index within the array where the item is found, we can just do

find(data, 100, 12) - data

Remember that pointer subtraction gives the number of elements between them.

Do we need to delete the pointer returned by find? No! In fact, terrible things will happen if we do. The pointer returned by find is a pointer to inside an array; we only ever want to delete whole arrays. (And note that find will work on static arrays, which we don’t ever want to delete at all.)

One nice this about using pointers as arrays is that it lets us lie about how big an array is. E.g., suppose we had the array

int arr[] = {1, 5, 2, 7, 5, 2, 8, 5, 2};

And we wanted to find the sum of elements 2 through 5. We can use sum to do this: we just give it a pointer to arr[2] as the “start” of the array, and tell it that the size is 4:

int x = sum(arr + 2, 4); // We could also write &arr[2]

sum doesn’t know that the array is actually bigger, that there’s more of it that it can’t see. Sometimes, we can use this to simplify our code.

Let’s step up our game a bit. Suppose I give you a sorted array, in ascending order:

int arr[] = {1, 2, 5, 6, 8, 9, 11, 15, 17, 20, 21};

and we want to find a particular element in this array, say, 11. Can we do better than just scanning through the array from beginning to end? As a hint, look at middle element, 9. What can you say about where 11 will be, based on the fact that the middle element is 9?

11 must be after 9 in the array. Because the array is sorted, we know that everything before 9 will be less than or equal to 9, so we can exclude that entire region of the array from our search. We can exploit this to write a find that will work faster on sorted arrays:

int* find_sorted(int value, int* begin, int* end) {
  int* b = begin;
  int* e = end;

  while(begin <= end) {
    int* middle = begin + (end - begin) / 2; // Pointer to the middle element

    if(*middle == value)
      return middle;
    else if(*middle < value) {
      end = middle - 1;
    }
    else if(*middle > value) {
      begin = middle + 1;
    }
  }

  return nullptr; // Not found
}

This is called a binary search. At each step, we cut the amount of things we have to search through in half. Contrast this with the earlier find, where at each step, we only reduced the amount of things we had to search through by 1.

Also note that we can use both find and sorted_find on “sub-arrays”. If the pointers we give them are not for the whole of an array, but just for a part, they don’t care.

new and delete are dangerous

It’s true, they are. The reason they are dangerous is that it’s very easy to forget to delete something, or let the only pointer to it go out of scope, etc. However it happens, you now have a memory leak. If you write a function like this:

void my_function() {
  int* stuff = new int[10]();
  //.. does some stuff
  // does NOT delete stuff
}

Every time you run this function, you leak 10 ints worth of memory. Your program will never get that memory back; the only way to get it back is to close your program. Contrast this with something like

void my_function() {
  vector<int> stuff(10);
  //...

  // stuff is automatically freed here
}

You should prefer structures like vector and string that manage their own memory, rather than trying to roll your own. The only time you should be using new and delete are when you need pointers (sometimes) or when you are actually creating your own data type. If you are building vector yourself, you can use new and delete to do so.

Old-style strings

In C (and in very old C++), before string was invented, strings were represented as dynamically allocated char arrays (i.e., as char*). Because people were lazy and didn’t want to pass the length of the string around, they came up with the idea of marking the end of the string with a special character: the null character, \0. That is, every string would actually look something like this:

"Hello, world!\0"

If we wanted to know the length of the string, we just scan down it until we find the \0, counting characters as we go.

The header <cstring> contains a number of functions for manipulating these kinds of “strings”, in particular, strlen which finds the length of a string.

Let’s use this to write a function to append one char* string onto the end of another. That is, we’re going to write s1.append(s2) for char* style strings.

Before we can create a dynamically-allocated array, we have to know how big to make it. So we need to know the length of the string that will result from appending s1 to s2:

char* append(char* s1, char* s2) {
  int l1 = strlen(s1), l2 = strlen(s2);
  char* out = new char[l1 + l2];

  // Copy all the elements of s1
  for(int i = 0; i < l1; i++)
    out[i] = s1[i];

  // Copy all the elements of s2
  for(int j = 0; k < l2; j++)
    out[j + l1] = s2[j];

  return out;
}

Old-style strings were very dangerous; all sorts of bugs and exploits resulted from accidentally writing strings into arrays that weren’t allocated big enough to hold them. Nonetheless, there’s still a lot of old-style code floating around (esp. in C, but even in C++). Note that string will even give you access to the char* representing its text:

string name = "Andy Clifton";
name.c_str() // Gives the null-terminated char* representing "Andy Clifton\0";