References and pointers

Review: Arrays and Vectors

Vectors and arrays: Last time, a long time ago, we talked about vectors and arrays. To recap:

To work through an example, let’s say I have a vector

vector<float> data = { 0.1, -2.3, 4.5, 3.9 };

And I want to:

  1. Delete the middle two values.

  2. Add the new value -8.3 to the end

  3. Insert the values 1.3, 5.7, -3.8 before the first value

data.erase(1,2);
data.push_back(-8.3);

// We could do this with three separate inserts, as well
vector<float> more_data = {1.3, 5.7, -3.8};
data.insert(0, more_data);

Two-dimensional vectors and arrays

Sometimes we need to store a two-dimensional arrangement of data. For example, in order to store an image, we must store the color at each pixel, and pixels are arranged in a two-dimensional grid. In general, two-dimensional vectors/arrays can be visualized as grids.

(draw example)

However, as we will see, the optimal arrangement for this is quite different, internally.

There are two ways to store a two-dimensional array/vector:

Constructing an array of arrays is relatively easy:

int a[8][8]; // 8x8 array of arrays

Likewise, a vector of vectors can be constructed, somewhat more obscurely, as

vector<vector<int>> b(8, vector<int>(8));

(We are actually using the “fill” method, where each of the 8 rows is filled with 8 vector<int>(8)s; i.e., with empty rows of length 8.)

To access a particular element x,y we just write

a[x][y]       // for arrays
b.at(x).at(y) // for vectors

Most of the vector operations don’t make sense for a vector-of-vectors (at least, not for one where we intend to keep the size fixed, and all the rows the same length).

An array-of-arrays will contain undefined data when it is first created. A vector of vectors will contain the “default value” for its element type; for numbers this is 0. Thus, vectors are somewhat safer in that it is impossible to use them “uninitialized”.

Doing anything interesting with two (or more) dimensional arrays/vectors generally requires loops, which we’ll cover later.

Storing an array-of-arrays (or a vector-of-vectors) has a few disadvantages

The other way of storing an \(m \times n\) grid is as an array/vector with exactly \(mn\) elements. How can we map x and y to the index into this? Well, time for a puzzle:

Draw 3x3, 4x4, 5x5 grids with elements numbered sequentially. Given a particular x and y, how can we compute the i (index), written in each cell?

The solution is 

i = x + y*width;

Note that we don’t care how tall the grid is, just how wide.

This arrangement is called row-major ordering, because the elements of the rows are listed in order. (in order to go left/right in a row, you just move to the next/prev element. In order to move down/up a column, you have to skip ahead/back by width.) Also note that, unlike the way we usually draw a 2D coordinate space, this layout has positive Y moving down.

The row-major ordering is common for images, games, etc. It trades a bit of (easy) math for better space usage.

We can actually extend row-major ordering to 3 (or more) dimensions. E.g., if we have x, y, and z, along with width, height, and depth then we have the computation

i = x + y*width + (width*height)*z

The general computation, if we have coordinates \(d_1, d_2, \ldots\) and dimensions \(D_1, D_2, \ldots\) is

$$i = d_1 + d_2 D_1 + d_3 D_1 D_2 \ldots + d_n (D_{n-1} D_{n-2} \ldots D_2 D_1)$$

Another puzzle:

Given i and width, can you recover x and y?

Parallel arrays and vectors

If an array or vector corresponds to a table with two columns (one of which is always “Number”) then parallel arrays/vectors give us a way to add more columns.

The idea of a parallel vector/array is when we need to associate more than one piece of information with a particular index. Normally, a vector or array associates a single piece of data (e.g., a string, float, int, etc.) with each index. Suppose, for example, we want to maintain a table of Fullerton College faculty, with names and a bool indicating whether or not they have tenure. A parallel vector for this might look like:

vector<string> names =    { "Andy Clifton", "Scott Edwards", "Caleb Petrie" };
vector<bool> has_tenure = { false,          true,            false };

Each particular index (e.g., 0) is assigned to a single “record”, so names[0] contains my name, while has_tenure[0] says whether or not I have tenure (I don’t). This corresponds to the table:

Number Name Has Tenure
0 Andy Clifton false
1 Scott Edwards true
2 Caleb Petrie false

Later on we’ll see a much better way of organizing “aggregate” data like this, but for now, it gives us a good way of associating things together: just make sure the associated items are all at the same index (number).

In general, we’ll assign the number of the thing we are interested to a variable (e.g., i), then we can get all the associated information with

names[i]
has_tenure[i]
office[i]
// etc.

Remember that there’s no relationship between elements with different indices. E.g., it makes no sense to look at

names[i]
has_tenure[i+1]
office[i-1]

On the other hand, since an index identifies a particular person (in this example), we can easily create another column that “points to” a person. Suppose we wanted to store each person’s supervisor. The other person is identified by their own number, so we have the table:

Number Name Has Tenure Supervisor
0 Andy C. false 1
1 Scott E. true …

Thus, we can easily build “tables” where the rows refer to each other.

Like I said, later on, we’ll see a much better way of building things like this. We will esentially create our own “type” (just as int and float and string are types) faculty that will contain within it all the information associated with a particular faculty member. Thus, instead of being scattered over several different arrays, we will just create an array of faculty and each element of that array will have everything we need for that person. Really, in C++ there’s almost no reason to use parallel arrays; I’m only showing them to you so you know what they are, if someone refers to them.

References

Suppose we wanted to write a function that would take two ints and swap (exchange) them. We might try something like this:

void swap(int x, int y) {
  int t = x; 
  y = x;
  x = t;
}
...
// Later
int a = 4, b = 5;
swap(a,b);
// What are a and b now?

(Why do I need t?)

Will this work? No! Remember that the boxes created for the parameters x and y only receive copies of the values from a and b. After that, the connection end. So while this will swap the values in x and y, they go out of scope at the end of swap, and a and b are unaffected. What we really want is a way for x and y to just be “aliases”, other names, for a and b. Today we’re going to look at two elements that let us do that.

A reference is just another name for an existing box. For example:

int a = 1;
int& b = a;

The & after int is part of the type: you should read this as “reference to int”. In this code, the box for a actually has two names: a and b. Changes to b will affect a, and vice versa, because they both actually refer to the same box. E.g.

b = 12; 
a == 12; // True!
b++;     // a = 13
a = b;   // doesn't change anything

You can create a reference to any existing thing:

int a = 1;
int& b = a; // Reference to int
string s = "Hello";
string& sr = s; // Reference to string

char& cr = s.at(0); // Reference to char!

vector<int> vs = {1, 2, 3};
vector<int>& vr = vs; // Reference to vector<int>
int& vre = vs.at(1); // Reference to the second element of vs

This is another form of indirection. When we use a reference, we don’t have to know what it’s refering to. As shown above, we can even create references to the boxes inside vectors and strings!

Note that you can’t create a reference to a value:

int& a = 12; // Error!

If a reference is another name for a box, that means the other box must already exist. There’s even a technical name in C++ for “things you can get a reference to”: lvalue. The “l” is for “left”, as in, things that can be on the left side of an assignment.

References can also be created to other references:

int a = 12;
int& b = a; // A reference to a
int& c = b; // Another reference to a

(draw box)

As shown, references-to-references “collapse” to the original, non-reference variable. You also use only one & for a reference-to-reference; you don’t keep adding them for each layer of indirection.

Now that we’ve got references, let’s walk through some code using them:

int a = 1, b = 2, c = 3;
int&d = b;
int&e = a;
d += c;
b *= d + c;
d *= a + c;
e = a * b * (c - e);

How many boxes will I need, and what will be their values? It’s not so simple as counting variable declarations, because references don’t get their own boxes, so I only need three boxes.

Unfortunately, it’s not possible to create an array/vector of references, for some technical reason.

References give us a new power when combined with ranged for loops:

vector<int> vs = {...};
for(int& e : vs)
  e *= e;

This loop will square all the contents of vs. If we had left the & off, it wouldn’t do anything, because each value taken on by e would be a copy of the corresponding value in vs. With references, e is always a reference to some element of vs, and thus modifying e modifies the element itself.

References and functions

References like this are kind of useless, because we already know what they refer to, so we could just use that. Instead of writing b = 12 we could just replace it with a = 12, because we know that b is a reference to a. The real power of references comes when they are combined with functions: a function can take any of its arguments as references, in which case it doesn’t get a copy of the original thing, rather, that parameter becomes another name for the original thing. This means we can write functions which modify their arguments:

void cleanse(vector<int> vs) {
  vs.clear(); 
}

void purge(vector<int>& vs) {
  vs.clear(); 
}

int main() {
  vector<int> data = {1, 2, 3};

  cleanse(data); // Does nothing, parameter is a copy

  purge(data); // Deletes everything in data, because param. is a ref.
}

In the previous class, we looked at a function which reverses a vector. In that case, we had to build it to construct a new vector and return that, but now we can build one to reverse “in place”:

void reverse(vector<int>& vs) {
  int i = 0;
  int j = vs.size()-1;
  while(i < j) {

    // Swap
    int temp = vs.at(i);
    vs.at(i) = vs.at(j);
    vs.at(j) = temp;

    i++;
    j--;
  }
}

In fact, if we want to, we can split the “swap two things” behavior off into another function:

void swap(int& a, int& b) {
  int temp;
  temp = a;
  a = b;
  b = temp;
}

and then we just have

void reverse(vector<int>& vs) {
  int i = 0;
  int j = vs.size()-1;
  while(i < j) {

    swap(vs.at(i), vs.at(j));

    i++;
    j--;
  }
}

Using this, 

int main() {
  vector<int> data = { 1, 2, 3 };
  reverse(data);
  // Now data = {3, 2, 1}
}

Note that the same restriction on creating vectors to existing boxes applies here. E.g., you will get an error if you try to do

swap(1,2);

because those are not existing boxes.

As an example, let’s use swap to solve an interesting problem: sorting a 4-element vector. The basic idea is that we’re going to write a function that acts like a comparator. A comparator is an electrical component that takes in two signals, compares their voltage levels, and outputs the lower one, and the higher one. In other words, it compares two things and if they are out of order, it swaps them.

Using references, we can write a function compare_and_swap that does just this:

void compare_and_swap(int& a, int& b) {
  if(a > b) {
    int temp = a;
    a = b;
    b = temp;
  }
}

Suppose I have the vector v = {3, 4, 2, 1} and I want to sort it. A first step would be to compare-and-swap successive pairs of elements. So we’d do

compare_and_swap(v.at(0), v.at(1));
compare_and_swap(v.at(1), v.at(2));
compare_and_swap(v.at(2), v.at(3));

What is the state of my vector after this: {3, 2, 1, 4}. Notice that the largest element has been moved to the end of the vector. Because the swaps overlap, they will have the effect of “pushing” the largest element up to the top, which is just where it’s supposed to be in the sorted version. So now the last (largest) element is in place, now I only have 3 things to sort. How am I going to do that? The exact same way:

compare_and_swap(v.at(0), v.at(1));
compare_and_swap(v.at(1), v.at(2));

Now we have {2, 1, 3, 4}. The last two elements are in the right place. All that remains is to compare-and-swap the first two, and we’re done. The complete procedure looks like this:

compare_and_swap(v.at(0), v.at(1));
compare_and_swap(v.at(1), v.at(2));
compare_and_swap(v.at(2), v.at(3));

compare_and_swap(v.at(0), v.at(1));
compare_and_swap(v.at(1), v.at(2));

compare_and_swap(v.at(0), v.at(1));

This is known as a bubble sort, because the larger values “bubble” up to the end of the sequence. We could, of course, write a pair of nested loops, which would work to sort a sequence of any size.

Parameter passing schemes

We now have two ways of passing things to functions:

Both are useful, in their own way:

A function can even return a reference:

int& select(bool which, int& true_value, int& false_value) {
  if(which == true)
    return true_value;
  else
    return false_value;
}

We can use this like so:

int a = 1, b = 2;

select(true,a,b) = 5; // Sets a to 5
select(false,a,b)++;  // Sets b to 3

Let’s look at an example of functions-with-references in action. We’ll do this example both ways, as a function, and as a reference. This is the “puzzle” from problem set 4. The task is to run the following until \(n = 1\)

The Collatz conjecture states that for any starting \(n\), we’ll always eventually end up at 1. E.g., if we start at 5:

The non-reference version will use a function collatz that takes n and returns the new n; main will have to check and see if it is 1:

int main() {
  cout << "Enter n: ";
  int n;
  cin >> n;

  int steps = 0;
  while(n > 1) {
    n = collatz(n);
    steps++;
  }

  cout << "It took " << steps << " steps to reach 1." << endl;
  return 0;
}

int collatz(int n) {
  if(n % 2 == 0)
    return n / 2;
  else
    return 3 * n + 1;
}

The reference version will have collatz directly modify n. This means that it can return something other than n, so we can make it return a bool, true if n > 1 (i.e., continue running) or false if n <= 1. 

int main() {
  cout << "Enter n: ";
  int n;
  cin >> n;

  int steps = 0;
  while(collatz(n)) 
    steps++;

  cout << "It took " << steps << " steps to reach 1." << endl;
  return 0;
}

bool collatz(int& n) {
  if(n % 2 == 0)
    n = n / 2;
  else
    n = 3 * n + 1;

  return n > 1;
}

Which one your prefer is partly a matter of style. Note that there are some limitations to the reference one. E.g., suppose we wanted to run collatz two steps at a time, to find the end result faster. In the non-reference version, we could just do

n = collatz(collatz(n)); // Skip 2 steps ahead

But in the reference version this won’t work. We have to write

collatz(n);
collatz(n);

It’s mostly a matter of whether you prefer to think about things “mathematically”, as expressions and functions that take inputs and give back outputs, or “procedurally”, of functions as statements, that do things.

References for “out” parameters

Another use for references is when we want to return multiple values. E.g., if we wanted to return both the largest and smallest, we could write

void bounds(vector<int> vs, int& smallest, int& largest) {
  smallest = largest = vs.at(0);
  for(int e : vs) {
    if(e > l)
      l = e;
    if(e < s)
      s = e;
    }
  }
}

and now it will work. (But note, as we’ll see later, there are better ways of returning multiple values.)

Pointers

A pointer is a reference that you can “re-point”. This adds some complexity, as now we have to distinguish between

We didn’t have this problem with references, because once a reference is created, it cannot be “changed”; all operations on it affect the target, so there’s no ambiguity. This also means that when we create a pointer, we have to use some extra syntax to set what it’s pointing to.

An additional source of difficulty comes from the fact that pointers use the same notation as references, but for a totally different purpose: pointers use & as an operator, part of an expression, while references use & as part of a type. It’s important to keep the difference clear: if you see & in the type part of a variable declaration, it means you are dealing with a reference. If you see it in an expression, then you are dealing with a pointer.

To create a pointer to a we do this:

int a = 1;
int* b = &a;

int* is the type, you should read this as “pointer to int”. The &a should be read as “pointer to a”. Note that both of these are incorrect:

int a = 1;
int* b = a;  // WRONG: a is int, b is pointer-to-int
int  b = &a; // WRONG: a is pointer-to-int, b is int
int& b = &a; // WRONG: a is pointer-to-int, b is reference-to-int

We can change what a pointer points to by just assigning to it:

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

A pointer can also point to nothing at all, if we set it to nullptr:

int* c = nullptr;

A pointer that contains nullptr is called a null pointer. Trying to look at the “other end” of a null pointer is an error called a “null pointer dereference”.

One interesting thing about pointers is that you can treat them like true/false (i.e., bool) values. nullptr counts as false, and anything else counts as true. This means you can do something like

if(c) 
  // Access the other end of c
else
  // Don't use c, it's not safe

Speaking of looking at the other end, how do we do that? If c is a pointer, then just plain c refers to the pointer itself. (*c) refers to the thing on the “other end” of the pointer:

int a = 1;
int* b = &a;
(*b) = 2;     // Now a = 2
(*b)++;       // Now a = 3;
cout << (*b); // Prints 3

Note the way these work with respect to their types. Suppose we have

int a = 1;
int* b = &a;

Then we have the following types:

In other words, putting a * before a variable removes on layer of “pointer-to”. Putting a & before a variable adds an additional layer of “pointer-to”. This is true if we use more than one:

int a = 1;
int* b = &a;    // b is pointer-to-int
int** c = &b;  // c is pointer-to-pointer-to-int

*b = 12;        // *b is int
**c = 13;       // **c is int (*c is pointer-to-int)

It’s extremely important to keep these type rules in mind when working with pointers. 99% of the errors that occur when using pointers come from not thinking about the types: mixing up pointers of different levels.

How pointers work

Internally, every “box” (i.e., every non-reference variable) is located somewhere in memory, at some address. A pointer is just a variable that contains an address. (Draw example). When we write &a we are really asking for the address of a. Similarly, when we write *p we are saying, don’t look at p itself, look at the things whose address it contains.

Within an array, vector, or string, the elements are located in successive addresses, so incrementing a pointer just moves from one address to the next.

Operations on pointers

Pointers support various operations on the pointers themselves, as opposed to whatever operations the pointed-to type supports (assume that a and b are both pointers to the same type):

Operation Description
a == b Do a and b point to the same thing?
a != b Do a and b point to different things?
a++ Make a point to the “next” thing (see arrays, below)
a-- Make a point to the previous thing
a += n Move a ahead n items
a < b Is a before b (see pointers-to-arrays, below)?
a - b Find the distance between a and b

Note that a == b is different from *a == *b. The former asks, do a and b point to the same thing? While the latter asks, are the things pointed to by a and b the same? If a == b it is guaranteed that *a == *b, but the converse is not the case. E.g.,

int a = 1, b = 1;
int* c = &a, * d = &b;

*c == *d; // True, 1 == 1
c == d;   // False, a and b are different boxes

Pointers and arrays

The above table contains several operations for “moving” pointers, comparing pointers, subtracting pointers, etc. All of these are only valid for pairs of pointers that point to elements within the same array or vector. To get a pointer to an array element you can do

int data[5];

int* p = &data[1]; 
int* q = data + 1; // same thing

For a vector, you have to use

vector<int> values(10);
int* r = &values.at(1);

In either case, you can move the pointer forwards and backwards:

p++; // Now p points to data[2]
p += 2; // Now p points to data[4]
r--; // Now r points to values.at(0)

If we have two pointers to the same array/vector, we can compare them to see which one points to the earlier element:

int data[10];
int* p = data + 2, *q = data + 4;
p < q  // True
p >= q // false
q - p  // gives 2

Pointers to array/vector elements give us another way to write a loop over an array. Suppose we have an array 

int data[10];

Then we can do

for(int* p = data + 0; p != data + 10; p++)
  cout << *p << endl;

(With vectors its a little more complicated, because we can’t do data.at(10) without causing an error.)

You can do the same things with strings:

string name = "Andy Clifton";
char* c = *name.at(0); // c points to 'A'
c++;                   // c points to 'n'

Once again, these operations are only valid on pointers to array elements! In particular, the result of this is undefined:

int a;
int* b = &a;
b++; // ???

It may do nothing, it may cause your computer to explode.

Examples

We can write versions of both the swap and compare_and_swap functions, above, that take pointers. Note than when we use these, we will have to remember to write

int a,b, x,y;
...
swap(&a, &b);
compare_and_swap(&x, &y);

unlike with the reference-based versions.

void swap(int* a, int *b) {
  int t = *a;
  *a = *b;
  *b = t;
}

void compare_and_swap(int *a, int *b) {
  if(*a > *b)
    swap(a,b); // a and b are already pointers.
}

References vs. pointers

When should you use references, and when should you use pointers? The general rule is, use references if you can, pointers when you must.

Of course, if you don’t need any indirection at all, then you should use neither; just stick with plain ol’ values.

Note that you can mix and match pointers and references, creating a reference to a pointer to int, for example:

int a = 1, b = 2;
int* c = &a;
int*& d = c; 

*c = 2; // a = 2;
*d = 3; // a = 3;
d = &b; // Now both d and c point to b

A pointer-to-refrerence-to-type is just a pointer to type:

int a = 1;
int& b = a;
int* c = &b; // &b is the same as &a, so c points to a

Parameters to main

Other functions can have parameters, can main? Kind of. Remember that main is the entry point of your program. So if main had parameters, where would they come from? The answer is, from the operating system. Normally, we run our programs like this:

./program

but you can actually put things after the name of the program:

./program one 1 two 2

These are called command-line arguments. There are two forms that the main function can take: the one we’ve been using

int main()

and this one:

int main(int argc, char** argv)

The char** looks a little funny; it is in fact a pointer-to-pointer-to-char. That sounds bad, but you can think of it as an array (passed as a pointer) of char*‘s, where a char* is kind of like an old-fashioned string. You can convert a char* into a string. Here’s an example that prints out all the elements of the array:

#include <iostream>
#include <string>
using namespace std;

int main(int argc, char** argv) {
    for(int i = 0; i < argc; i++) {
        string arg = argv[i];
        cout << arg << endl;
    }
    return 0;
}

If we run this on the above program with arguments one 1 two 2 it will print out something like this:

/home/aclifton/work/program
one
1
two
2

In fact, argv is always one more than the number of arguments on the command-line, because the first entry is always the full path to the program itself. If you write a program that needs to know “where it is”, you can use this to find it.

A lot of the commands you use on the command-line are just programs that use this to look at their arguments. E.g., the web-serve program that one of the projects uses works like this:

web-serve ./myprogram

but it’s just a normal C++ program (that I wrote) that takes, as a command-line argument, the name of another program!

Pointers and arrays

A pointer to an element of a vector, string, or array has some special properties: we can move it around within its container without using the address-of operator. An example:

vector<int> v = {1, 1, 2, 3, 5};
int* p = &v.at(0);
++p;    // Move p forward 1 element, p points to v.at(1)
--p;    // Move p back 1 element, p points to v.at(0)
p += 2; // Move forward by 2 elements, v.at(2)
int* q = &v.back(); // i.e., v.at(4);
q - p   // evaluates to 2: &v.at(4) - &v.at(2)

Note that none of the above changes the values inside the vector. After executing the above code, the vector still contains 1, 1, 2, 3, 5; only the pointers p and q have moved around “within” the vector.

A pointer into a vector/string/array represents a “position”, but one that implicitly keeps track of the vector/string/array. Put another way, right now, if we want to write a function to process an element of a vector, we need to pass it two parameters:

Given these two things, we can move around within the vector to process other elements. With pointers, we can just pass a int* and it contains (almost) everything we need to access the rest of the vector.

Because pointers-to-container-elements represent positions, we can do various things with them to manipulate those positions:

Pointer invalidation

If you are using pointers into a string or vector, you should be careful to avoid also using .push_back, .pop_back, .insert, or any other operations that change the size of the container. The reason for this is that sometimes, C++ cannot simply grow or shrink the vector “in place”, but must re-create it from scratch. If this happens (and C++ is allowed to do it any time you use a size-changing operation), then the entire vector/string is copied in memory from one location to another, and all of your pointers will still be pointed at the old, no longer used contents of the vector. These pointers have been invalidated, the same as if they were pointing at a variable which had gone out of scope. Using them will either produce garbage results, or crash your program.

In general, you should only use pointers into strings/vectors if you are certain the size will not change; do all of your .push_backs or whatever first, and then use pointers.