Appendix A

Intermediate C++ Review

This appendix provides a quick review of intermediate C++ concepts used throughout the book. The concepts roughly correspond to typical topics in Computer Science 1 and 2 courses. If you are rusty with C++, you should spend extra time reviewing this material.

int i = 20;
int& r = i; // r refers to i

By default, functions pass parameters by value (pass-by-value), meaning that when you call a function, the parameter copies to a new variable. When passing by value, modifications to parameters do not persist beyond the function call. For example, here is an (incorrect) implementation of a Swap function that swaps two integers:

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

The problem with Swap is that a and b are copies of the parameters, which means the function cannot truly swap the parameters as desired. To solve this problem, you should instead declare the parameters of Swap as references to integers:

Click here to view code image

void Swap(int& a, int& b)
{
   // (The body of the function is identical to the previous)
}

When passing a parameter by reference (pass-by-reference), any changes made to that parameter within the function will persist after the function ends.

One caveat is that because a and b are now references to integers, they must reference existing variables. You can’t pass in temporary values for the parameters. For example, Swap(50,100) is invalid because 50 and 100 are not declared variables.

Table A.1 shows code snippets and possible locations of their variables in memory. Notice that each variable has an associated memory address. The table shows the memory addresses in hexadecimal simply because that’s the typical notation for memory addresses.

The address-of operator (also &) queries the address of a variable. To get the address of a variable, place a & in front of the variable. For example, given the code in Table A.1, the following code outputs the value 0xC234:

std::cout << &y;

A pointer is a variable that stores an integral value corresponding to a memory address. The following line declares the pointer p that stores the memory address of the variable y:

int* p = &y;

The * after the type signifies a pointer. Table A.2 shows the pointer p in action. Note that, just like any other variable, p has both a memory address and a value. But because p is a pointer, its value corresponds to the memory address of y.

The * operator also dereferences a pointer. Dereferencing a pointer accesses the memory “pointed to” by the pointer. For example, the last line in Table A.3 changes the value of y to 42. This is because dereferencing p goes to the memory address 0xC234, which corresponds to the location of y in memory. Thus, writing the value 42 at this memory address overwrites the value of y.

Unlike references, which must refer to something, pointers can point to nothing. A pointer that points to nothing is a null pointer. To initialize a pointer as null, use the nullptr keyword, as in the following code:

char* ptr = nullptr;

Dereferencing a null pointer crashes the program. The error message varies depending on the operating system, but typically “access violation” or “segmentation fault” errors occur when dereferencing a null pointer.

int a[10];
a[0] = 50;

By default, the elements in an array are uninitialized. While you could manually initialize each element in an array, it’s more convenient to use either the initializer syntax or a loop. The initializer syntax uses braces, like this:

int fib[5] = { 0, 1, 1, 2, 3 };

Alternatively, you could use a loop. The following initializes each of the 50 elements in array to 0:

int array[50];
for (int i = 0; i < 50; i++)
{
   array[i] = 0;
}

C++ stores arrays contiguously in memory. This means that the data for index 0 is right next to the data for index 1, which is right next to index 2, and so on. Table A.4 shows an example of a five-element array in memory. Keep in mind that the variable array (without the subscript) references the memory address of index 0 (in this case, 0xF2E0). Because of this, you can pass a single-dimensional array to a function via a pointer.

You also can declare multidimensional arrays. For example, the following code creates a 2D array of floats with four rows and four columns:

float matrix[4][4];

To pass a multidimensional array into a function, you must explicitly specify the dimensions, like this:

Click here to view code image

void InvertMatrix(float m[4][4])
{
   // Code here...
}

First, the stack has a limited amount of memory available—typically much less than the amount of memory an average program might want to use. For example, the Microsoft Visual C++ compiler has a default stack size of 1 MB. Such a small amount of memory won’t be enough for all but the simplest games.

Second, local variables have a fixed lifetime. They are only available from the point of declaration until the end of the containing scope. This scope is typically within a function, as global variables are stylistically undesirable.

In dynamic memory allocation, the programmer controls allocation and deallocation of variables in memory. Dynamic allocations go into the heap, which is a separate part of memory. The heap is much larger in size compared to the stack (several gigabytes on current machines), and data on the heap persists until either the programmer deletes the data or the program ends.

Recall that in C++, the new and delete operators allocate and deallocate memory on the heap. The new operator allocates memory for the requested type of variable, and for classes and structs, it calls the constructor. The delete operator performs the opposite: It calls the destructor for class/struct types and deallocates the memory for the variable.

For example, this code dynamically allocates memory for a single int variable:

int* dynamicInt = new int;

To free the memory of a dynamically allocated variable, use delete:

delete dynamicInt;

Forgetting to delete a dynamically allocated variable causes a memory leak, meaning that the memory is unusable for the remaining life span of the program. For programs that run for a long time, small memory leaks accumulate over time and eventually cause the heap to run out of memory. If the heap runs out of memory, the program will almost always crash soon afterward.

Of course, dynamically allocating just a single integer doesn’t take advantage of all the available memory on the heap. You can also dynamically allocate arrays:

Click here to view code image

char* dynArray = new char[4*1024*1024];
dynArray[0] = 32; // Set the first element to 32

Note that when dynamically allocating an array, you place square brackets immediately after the type and specify the size there. Unlike with a statically allocated array, with a dynamically allocated array, you can specify a size at runtime.

To delete a dynamically allocated array, use delete[]:

delete[] dynArray;

However, one issue with references is that they allow the function to modify the parameter. For example, suppose an Intersects function takes in two Circle objects and returns whether these circles intersect. If the function takes in these circles by reference, it could choose to modify the centers or radii of the circles.

The solution is to instead use a constant (const) reference. A const reference guarantees that the function can only read from the reference but not write to it. So, a more correct declaration of Intersects uses const references:

Click here to view code image

bool Intersects(const Circle& a, const Circle& b);

You can also mark member functions as const member functions to guarantee that a member function does not modify member data. For example, a GetRadius function for Circle shouldn’t modify member data, which means it should be a const member function. To denote that a member function is const, add the const keyword immediately after the closing parenthesis of the function declaration, as in Listing A.1.

Listing A.1 Circle Class with const Member Function

Click here to view code image

---

class Circle
{
public:
   float GetRadius() const { return mRadius }
   // Other functions omitted
   // ...
private:
   Point mCenter;
   float mRadius;
};

---

To summarize, the best practices when it comes to references, const, and classes are as follows:

• Pass non-basic types by reference, const reference, or pointers, to avoid making copies.

• Pass by const reference when a function does not need to modify a reference parameter.

• Mark member functions that don’t modify data as const.

Listing A.2 A Complex Class

Click here to view code image

---

class Complex
{
public:
   Complex(float real, float imaginary)
      : mReal(real)
      , mImaginary(imaginary)
   { }
private:
   float mReal;
   float mImaginary;
};

---

Notice how the constructor for Complex takes two parameters. To dynamically allocate an instance of Complex, you must pass in these parameters:

Click here to view code image

Complex* c = new Complex(1.0f, 2.0f);

As with dynamic allocation of other types, the new operator returns a pointer to the dynamically allocated object. Given a pointer to an object, the -> operator accesses any public members. For example, if the Complex class had a public Negate member function that takes no parameters, the following would call the function on the object c:

c->Negate();

You can also dynamically allocate arrays of objects. This works only if the class has a default constructor (a constructor that takes in no parameters). This is because there’s no way to specify constructor parameters when dynamically allocating an array. If you don’t define any constructors for a class, C++ automatically creates a default constructor for you. However, if you declare a constructor that takes in parameters, then C++ will not automatically create a default constructor. In this case, if you want a default constructor you must declare it yourself. In the case of Complex, because you declared a non-default constructor, there is no default constructor.

Listing A.3 A Basic Declaration for DynamicArray

Click here to view code image

---

class DynamicArray
{
public:
   // Constructor takes in size of element
   DynamicArray(int size)
      : mSize(size)
      , mArray(nullptr)
   {
      mArray = new int[mSize];
   }
   // At function used to access an index
   int& At(int index) { return mArray[index]; }
private:
   int* mArray;
   int mSize;
};

---

With this DynamicArray class, you could create a dynamic array with 50 elements by using the following code:

DynamicArray scores(50);

However, as previously discussed, every call to new must have a matching call to delete. In this case, DynamicArray dynamically allocates an array in its constructor, but there’s no matching delete[] anywhere. This means that when the scores object goes out of scope, there is a memory leak.

The solution is to use another special member function called the destructor. The destructor is a member function that automatically runs when destroying the object. For objects allocated on the stack, this happens when the object goes out of scope. For dynamically allocated objects, the delete call on the object also invokes the destructor.

The destructor always has the same name as the class, except prefaced with a tilde (~). So for DynamicArray, this is the destructor:

DynamicArray::~DynamicArray()
{
   delete[] mArray;
}

If you add this destructor, when scores goes out of scope, the destructor deallocates mArray, eliminating the memory leak.

Click here to view code image

Complex c1 = Complex(5.0f, 3.5f);

You could then instantiate a second instance of Complex as a copy of c1:

Complex c2(c1);

In most cases, C++ provides a copy constructor implementation if the programmer doesn’t declare one. This default copy constructor directly copies all member data from the original object to the new object. For Complex, this works perfectly fine; for example, it means that c2.mReal and c2.mImaginary directly copy from the corresponding members of c1.

However, for classes with pointers to data, such as DynamicArray, directly copying member data doesn’t give the desired result. Suppose you run the following code:

Click here to view code image

DynamicArray array(50);
DynamicArray otherArray(array);

With the default copy constructor, you directly copy the mArray pointers rather than copying the underlying dynamically allocated array. This means that if you next modify otherArray, you also modify array at the same time! Figure A.1 illustrates this problematic behavior, called a shallow copy.

If the default copy constructor is insufficient, as is the case for DynamicArray, you must declare a custom copy constructor:

Click here to view code image

DynamicArray(const DynamicArray& other)
   : mSize(other.mSize)
   , mArray(nullptr)
{
   // Dynamically allocate my own data
   mArray = new int[mSize];
   // Copy from other's data
   for (int i = 0; i < mSize; i++)
   {
      mArray[i] = other.mArray[i];
   }
}

Note that the only parameter to the copy constructor is a const reference to another instance of the class. The implementation in this case dynamically allocates a new array and then copies over the data from the other DynamicArray. This is as a deep copy because the two objects now have separate underlying dynamically allocated arrays.

In general, classes that dynamically allocate data should implement the following member functions:

• A destructor to free the dynamically allocated memory

• A copy constructor to implement deep copies

• An assignment operator (discussed in the next section), also to implement deep copies

If it’s necessary to implement any of these three functions, then you should implement all three. This problem is so common in C++ that developers coined the term rule of three to remember it.

Click here to view code image

friend Complex operator+(const Complex& a, const Complex& b)
{
   return Complex(a.mReal + b.mReal,
                  a.mImaginary + b.mImaginary);
}

Here, the friend keyword means that operator+ is a standalone function that can access Complex’s private data. This is a typical declaration signature for binary operators.

After overloading the + operator, you can use it to add two complex objects, like so:

Complex result = c1 + c2;

You can also override binary comparison operators. The only difference is that these operators return a bool. For example, the following code overloads the == operator:

Click here to view code image

friend bool operator==(const Complex& a, const Complex& b)
{
   return (a.mReal == b.mReal) &&
      (a.mImaginary == b.mImaginary);
}

You can also overload the = operator (or assignment operator). As with the copy constructor, if you don’t specify an assignment operator, C++ gives you a default assignment operator that performs a shallow copy. So, you usually only need to overload the assignment operator in the “rule of three” case.

There’s one big difference between an assignment operator and a copy constructor. With a copy constructor, you’re constructing a new object as a copy of an existing one. With an assignment operator, you’re overwriting an already existing instance of an object. For example, the following code invokes the assignment operator for DynamicArray on the third line because the first line previously constructed a1:

Click here to view code image

DynamicArray a1(50);
DynamicArray a2(75);
a1 = a2;

Because the assignment operator overwrites an already existing instance with new values, it needs to deallocate any previously dynamically allocated data. For example, this is the correct implementation of the assignment operator for DynamicArray:

Click here to view code image

DynamicArray& operator=(const DynamicArray& other)
{
   // Delete existing data
   delete[] mArray;
   // Copy from other
   mSize = other.mSize;
   mArray = new int[mSize];
   for (int i = 0; i < mSize; i++)
   {
      mArray[i] = other.mArray[i];
   }
   // By convention, return *this
   return *this;
}

Note that the assignment operator is a member function of the class, not a standalone friend function. Also, by convention, the assignment operator returns a reference to the reassigned object. This allows for code (albeit ugly code) that chains assignments, such as the following:

a = b = c;

You can override nearly every operator in C++, including the subscript [] operator, new, and delete. However, with great power comes great responsibility. You should try to overload an operator only when it’s clear what the operator does. It makes sense that the + operator does addition, but you should avoid reassigning the meaning of an operator.

For example, some math libraries override | and ^ for the dot and cross products, even though | and ^ are the bitwise OR and bitwise XOR for integral types. Overusing operator overloading in this manner leads to code that is difficult to understand. Amusingly, the C++ library itself breaks this best practice: Streams overload the >> and << operators for input and output (which are bitshift operators for integral types).

Table A.5 lists the most common time complexities, from the fastest to the slowest. Algorithms that are exponential or slower are too slow to see real use beyond very small problem sizes.

Although Big-O notation says how an algorithm scales, for certain problem sizes, algorithms with worse time complexity may perform better. For example, a quick sort has an average time complexity of O(n log n), while an insertion sort has a time complexity of O(n2). However, for small problem sizes (such as n<20), the insertion sort has a faster execution time because it does not use recursion. Thus, it’s as important to consider the actual execution performance of an algorithm as its specific use case.

Click here to view code image

// #include <vector> to use std::vector
std::vector<float> vecOfFloats;
vecOfFloats.push_back(5.0f);  // Contents: { 5.0f }
vecOfFloats.push_back(7.5f);  // Contents: { 5.0f, 7.5f }
vecOfFloats.push_back(10.0f); // Contents: { 5.0f, 7.5f, 10.0f }

Once the vector has elements, you can use array subscript notation to access specific elements in the vector. So given the vector from the preceding snippet, vecOfFloats[2] accesses the third element in the vector, yielding 10.0f.

In the long run, insertion into the back of a vector averages out to O(1). However, because a vector exists in one contiguous block of memory, as in Figure A.2, insertion at an arbitrary position in the vector is O(n). Because of this, you should avoid arbitrary insertion into a vector. But an advantage of this contiguous memory layout is that accessing an element at an index is O(1).

Click here to view code image

// #include <list> to use std::list
std::list<int> myList;
myList.push_back(4);
myList.push_back(6);
myList.push_back(8);
myList.push_back(10);
myList.push_front(2);

Figure A.3 illustrates myList after completing all the insertions. Note that, by definition, the elements in the linked list are not next to each other in memory. One advantage of a linked list is that insertion to either end of the list is O(1). If you have a pointer to an element in the list, you can also insert before or after that element in O(1) time.

However, one disadvantage of a linked list is that accessing the nth element of the list is O(n). For this reason, the implementation of std::list does not allow indexing via array subscripting.

The following code inserts three elements into a queue and then removes each element from the queue, outputting the values:

Click here to view code image

// #include <queue> to use std::queue
std::queue<int> myQueue;
myQueue.push(10);
myQueue.push(20);
myQueue.push(30);
for (int i = 0; i < 3; i++)
{
   std::cout << myQueue.front() << ' ';
   myQueue.pop();
}

Because queues operate in a FIFO manner, the above code outputs the following:

10 20 30

The std::queue implementation guarantees O(1) time complexity for insertion, accessing the front element, and removal.

Click here to view code image

// Include <stack> to use std::stack
std::stack<int> myStack;
myStack.push(10);
myStack.push(20);
myStack.push(30);
for (int i = 0; i < 3; i++)
{
   std::cout << myStack.top() << ' ';
   myStack.pop();
}

Because of the LIFO behavior of a stack, the above code outputs the following:

30 20 10

As with queue, the major operations for std::stack all have constant time complexity.

Click here to view code image

// #include <map> to use std::map
std::map<int, std::string> months;
months.emplace(1, "January");
months.emplace(2, "February");
months.emplace(3, "March");
// ...

The easiest way to access an element from a map is by using the [] operator and passing in the key. For example, the following would output February:

std::cout << months[2];

However, this syntax works as expected only if the key is in the map. To determine if a key is in a map, use the find function. This returns an iterator to the element, if found. (We discuss iterators in a moment.)

Internally, the std::map implementation uses a balanced binary search tree. This means that std::map can find an element by key in O(log n) (logarithmic) time. Insertion and removal from the map are also logarithmic. Furthermore, due to the binary search tree, looping over the contents of a map is in ascending order of the keys.

The C++ hash map std::unordered_map has the same functions as std::map, just without any guaranteed ordering. To use the hash map class, use #include <unordered_map>.

One way to loop over these other containers is with an iterator, which is an object that helps traverse the collection. Every C++ STL collection supports iterators. Each collection has a begin function that returns an iterator to the first element and an end function that returns an iterator to the last element. The type of the iterator is the type of the collection followed by ::iterator. For example, the following code creates a list and then uses an iterator to loop over each element in the list:

Click here to view code image

std::list<int> numbers;
numbers.emplace_back(2);
numbers.emplace_back(4);
numbers.emplace_back(6);
for (std::list<int>::iterator iter = numbers.begin();
   iter != numbers.end();
   ++iter)
{
   std::cout << *iter << std::endl;
}

Note that the iterator is dereferenced with *, the same way a pointer is dereferenced. The syntax for looping over other collections with iterators is similar.

In the case of a map, the iterator actually points to a std::pair. So, given an iterator to an element in a map, you must use first and second to access the key and value, respectively. Returning to the months map from earlier, you can get an iterator to an element and output its data with the following code:

Click here to view code image

// Get an iterator to the element with the key 2
std::map<int, std::string> iter = months.find(2);
if (iter != months.end()) // This is only true if found
{
   std::cout << iter->first << std::endl; // Outputs 2
   std::cout << iter->second << std::endl; // Outputs February
}

Typing out the long type names for iterators is annoying. C++11 provides the auto keyword to help reduce this pain. auto tells the compiler to deduce the type of a variable for you, based on the assigned value. For example, because the begin function returns an iterator of a very specific type, auto can deduce that correct type. There is no performance penalty for using auto, though some programmers find the code harder to understand.

Using auto, you can rewrite the list loop as follows:

Click here to view code image

// auto is deduced to be std::list<int>::iterator
for (auto iter = numbers.begin();
   iter != numbers.end();
   ++iter)
{
   std::cout << *iter << std::endl;
}

The code in this book uses auto only when it provides a benefit in readability.

Even with auto, the code for looping via iterators is clunky. Many other programming languages provide a foreach construct for looping over collections. C++11 has a similar construct called a range-based for loop. To loop over the numbers list with a range-based for loop, use the following syntax:

Click here to view code image

for (int i : numbers)
{
   // i stores the element for the current loop iteration
   std::cout << i << std::endl;
}

This loop makes a copy of each element in the list as it iterates over it. However, you can also pass by reference if you want to modify elements in the collection. Similarly, you can use const references.

You can also use auto for the type when writing a range-based for loop. However, as with using an explicit type, this makes a copy of each element. However, you can also use const and & with auto, if needed.

One disadvantage of a range-based for loop is that you can’t add or remove elements in the collection during the loop. So, if you need this behavior, you must use another type of loop.

Both of Scott Meyers’s books are great resources for best practices in C++. They are short reads that provide many tips on how to achieve maximum effectiveness from C++ code.

There is also a great deal of information available on the C++ Standard Library. Bjarne Stroustrup, the creator of C++, devotes a large section of his book to the C++ collection implementations.

LearnCpp.com. Last modified April 28, 2016. http://www.learncpp.com.

Meyers, Scott. Effective C++, 3rd edition. Boston: Addison-Wesley, 2005.

Meyers, Scott. Effective Modern C++. Sebastopol: O’Reilly Media, 2014.

Prata, Stephen. C++ Primer Plus, 6th edition. Upper Saddle River: Addison-Wesley, 2012.

Roberts, Eric. Programming Abstractions in C++. Boston: Pearson, 2014.

Stroustrup, Bjarne. The C++ Programming Language, 4th edition. Upper Saddle River: Pearson, 2013.