In these notes we’re going to work through an interesting and useful example: creating a dynamic vector-like class. To do this, we’ll need to learn a little about pointers, arrays, and dynamic memory allocation.
Before we start writing our own vector-like class, we need to discuss how C++ handles dynamic memory allocation. Recall that C++ has three main regions of memory at run-time:
Static memory and stack memory alone is enough for some programs, but not all. Any program that uses, for example, arbitrary sized vectors or strings need to use the free store. The issue is that the amount of memory objects like vectors and strings need is both unpredictable and not known until the program runs.
The free store is accessed using new and delete:
Whenever you want some free store memory you request it with new (or new []), and when you are done it you give it back with delete (or delete[]).
Both new and delete work with pointers. In C++, a pointer is the type of variable that stores the address of a memory location. Pointers are powerful but error-prone. Pointers provide the ability read and write almost any memory location in a program, even parts of program we shouldn’t be allowed to access. Ensuring that we use pointers in a correct and safe is non- trivial, but is an essential part of becoming a competent C++ (or C) programmer.
Consider the following code:
double x = 3.14;
You can think of x as labelling a box in memory that contains the value 3.14. Since x is of type double, the box is only allowed to contain values of type double.
The box that contains 3.14 is really just a few bytes in computer memory. All memory of modern computers had an address. You can get the address of any memory location using the & operator:
double x = 3.14;
cout << "x is stored at address " << &x << endl;
When I run this code on my computer I get the following results:
$ ./pointer_example
x is stored at address 0xbfe45638
0xbfe45638 is a hexadecimal (aka, hex, or base-16) number; the leading 0x indicates this. This is the typical format for writing computer address.
If you run this code more than once you will usually get different results, e.g.:
$ ./pointer_example
x is stored at address 0xbfa94b58
$ ./pointer_example
x is stored at address 0xbfee4a88
The addresses are different because it is up to the computer’s operating system (OS) to decide where exactly a program should run in memory. There’s usually no guarantee about the exact place in memory where a program is run.
The fact that the exact addresses of variables differs each time you run the program means it is rarely useful to deal with specific memory addresses.
C++ also lets you store an address in a variable. For example:
double x = 3.14;
double* addr_x = &x;
cout << "x is stored at address " << addr_x << endl;
The variable addr_x stores the address of x. The type of addr_x is double*, which is pronounced “double pointer”, or “pointer to double”. The term pointer means “address” in this context, and so double* is the type of a variable that stores an address of a double.
Given a pointer (e.g. a variable of type double*), we can access the value of the double being pointed to like this:
// ...
cout << "x has the value " << *addr_x << endl;
addr_x stores the address of some double, and *addr_x is the value of that double``. For the sake of concreteness, suppose addr_x stores the value 782. That means that memory location 782 is where a double is stored. If you want to know that value of the double stored at location 782, then *addr_x tells you.
In general, if p is a pointer, then *p is the object it points to. You can use *p just like a regular variable of that type.
You can use pointers with any data type in C++. For example:
string name = "Emily";
string* addr_name = &name;
cout << "The string \"" << *addr_name << "\" is stored at address " << addr_name
<< endl;
Or:
int a = 5;
int* p = &a;
int* q = p;
cout << "The address of a is: " << &a << endl
<< "The value of pointer p is: " << p << endl
<< "The value of pointer q is: " << q << endl
<< "The value of *p is: " << *p << endl
<< "The value of *q is: " << *q << endl;
Notice here that we have two pointers to the same int. You can treat pointer values like integers, and so do regular arithmetic operations on them, such as comparisons, additions, etc.
Pointer definition notation is completely general, allowing you to make pointers to any type of object. For instance:
These small examples of pointers are a good way to learn how they work and test your understanding of them. But the main practical use we have for pointers in this course is for dealing with dynamically allocated arrays.
The reason we’ve been discussing pointers here is so that you must access the C++ free store via pointers. The operators new and new[] return a pointer to a new chunk of memory on the free store, while and delete and delete[] take a pointer to a previously allocated chunk of memory and gives it back to the free store (so it can be used in future calls to new or new[]).
In this course, we’ll mainly use the free store for allocating contiguous chunks of memory (i.e. arrays). For example, this statement allocates 5 contiguous ints worth of free store space:
int* arr = new int[5];
The expression new int[5] returns a pointer to the first int of this newly allocated contiguous chunk of memory.
Warning
It’s possible for new to fail because there is not enough memory left on the free store. This is an important possibility that you must check for in real-life programs, but we will simply ignore it here.
To access the memory arr refers to, we normally use square-bracket notation:
arr[0] = 1; // equivalent to *(arr + 0) = 1
arr[1] = 2; // equivalent to *(arr + 1) = 2
arr[2] = 3; // equivalent to *(arr + 2) = 3
arr[3] = 4; // equivalent to *(arr + 3) = 4
arr[4] = 5; // equivalent to *(arr + 4) = 5
When contiguous memory is accessed like this with square-bracket notation, we usually refer to it as being an array, i.e. we say that arr is an array.
Internally, arr stores the address of the first int of the array. The address of the second int of the array is arr + 1, the address of the third int is arr + 2, and so on. In general, arr + i is the address of the (i+1)th int of arr, while the expression *(arr + i) is the value stored at address arr + i. The square-bracket notation is just shorthand for this, i.e. arr[i]``is equivalent to ``*(arr + i).
It is up to the programmer to keep track of the size of the array. Arrats in C++ are just contiguous chunks of memory, and so have no special features.
Keep in mind that low-level arrays do no bounds checking, and so you can access memory locations outside of the array:
arr[-3] = 2; // bad! Equivalent to *(arr - 3) = 2
arr[754] = 6; // bad! Equivalent to *(arr + 754) = 6
This kind of unrestricted use of pointers is almost always a very bad idea, and is the source of many errors and security problems. For instance, hackers have been known to use tricks like “stack smashing” and “buffer over runs” that given them access forbidden memory locations by indexing past the end of an array being used as a stack or buffer. Most other programming languages don’t allow programmers to do arbitrary pointer arithmetic.
An important property of free store memory is that it remains allocated until the programmer explicitly de-allocates using delete (or delete []). If delete is never called, then C++ assumes the memory is still being used by your the program ends. This may or may not be a problem depending on how much memory your computer has and your program needs.
Note
A program that does not de-allocate free store memory it no longer needs is said to have a memory leak. The problem is that while your program might have a lot of free memory to burn when it starts, eventually it will run out of memory if it keeps calling new without also calling delete to give it back. Memory leaks can be very difficult to debug in practice because it can take so long for them to become a problem. For instance, the Firefox web browser famously suffered from a number of hard-to- fix memory leaks for years.
Here’s how we de-allocate the memory used by arr:
int* arr = new int[5];
// ... use arr ...
delete[] arr; // delete[] needs a pointer to the memory it is deleting
It’s important to write delete [] with the [] because we allocated arr using new []. It would corrupt the free store if you wrote delete arr instead (delete without the [] only de-allocates the first element of the array).
You also need to make sure that you don’t ever delete the same free store memory twice. Again, that will likely corrupt the free store. For example, this is a bad mistake:
int* arr = new int[5]; // arr allocated
delete[] arr; // okay: arr de-allocated
delete[] arr; // oops: disaster!
To summarize, it is up to the programmer to remember to always:
In practice, it turns out to be surprisingly difficult to always follow these steps every time you use the free store. Free store errors form one of the largest and most subtle classes of bugs in C++, and so it is wise to do whatever we can to simplify free store management.
Note
Some programming languages, such as Java, use a special program called a garbage collector to (essentially) automatically delete unused memory. In such languages, programmers only ever need to allocate memory, and never need to manually delete it. While this can cause some performance penalties, in general garbage collection is extremely useful and prevents numerous hard-to-debug memory-allocation errors.
While you can use new and delete anywhere in your programs, in C++ it is wise to to encapsulate them in a class and let constructors and destructors call them automatically at the right time.
To see this, lets create our own vector-like class that will, when it’s done, we’ll be able to write code like this:
{
myvec arr(5); // create a myvec of 5 double
// all locations in arr initialized to 0 automatically
arr.set(3, 4.2); // set location 2 to be the value 4.2
for(int i = 0; i < arr.size(); ++i) {
cout << arr.get(i) << " ";
}
cout << endl;
} // arr is now out of scope, and so it's destructor is called
// which de-allocates its underlying array
Here is the myvec class:
class myvec {
double* arr; // pointer to the first element of the underlying array
int n; // size of this myvec
public:
myvec(int size) : n(size), arr(new double[]) { // constructor
for(int i = 0; i < n; ++i) {
arr[i] = 0;
}
}
int size() const {
return n;
}
void set(int i, double val) {
arr[i] = val;
}
double get(int i) const {
return arr[i];
}
~myvec() { // destructor
delete[] arr;
}
}; // class myvec
Note the following:
This is an elegant solution to the problem of managing free store memory, at least for array-like classes. The constructor and destructor work together to properly allocate and de-allocate the memory arr without any special effort on the part of the programmer using the class.
A class like the standard vector is essentially a myvec with many extra features. We’ll see how to implement some of those features in the notes that follow.
One improvement we can make to myvec is to add range-checking for set and get:
void set(int i, double val) {
if (i < 0 || i >= n) error("range error");
arr[i] = val;
}
double get(int i) const {
if (i < 0 || i >= n) error("range error");
return arr[i];
}
Range checking does slow these functions down a little, but out-of-range errors are so common and potentially dangerous (i.e. C++ lets you access memory past the end of the allocated array!) that the benefits of doing this often outweigh the costs.
A related change we ought to make is to check that the initial size passed into the constructor is not negative:
myvec(int size) : n(size), arr(0) { // constructor
if (n < 0) error("negative size array");
arr = new double[n];
for(int i = 0; i < n; ++i) {
arr[i] = 0;
}
}
In the initialization list we assign 0 to arr. For pointers, 0 is called the null pointer, i.e. a pointer that does not point to any particular value. We do this because we should not allocate memory for arr until we’re sure n is non-negative.
An important feature of the standard C++ vector is that it is dynamic: it’s size increases to accommodate new elements (it can also shrink, if necessary, but that is less common than growing — we will only deal with increasing size in these notes). Thus we can add elements as we get them, letting the vector automatically grow to hold them.
So lets make myvec dynamic. How can we do this? This requires some thought, because there is no way to make a low-level arrays (like arr) grow or shrink: they’re fixed in size.
The trick we’ll use is conceptually simple once you think of it: copy the array into a new, bigger array whenever the vector needs more space. When myvec needs space for new elements, we will do the following:
These steps are relatively expensive, and so we don’t want to do them too often. For instance, it would be terribly inefficient to create a new underlying array every time we added a new element. So instead, when the vector increases we will always allocate more memory than we need in order to minimize the number of new arrays we create.
A related detail is that the size of the vector and the size of the underlying array might be different. We’ll need to keep track of both.
Here is the updated class:
class myvec {
double* arr; // pointer to the first element of this myvec
int capacity; // number of elements arr can hold (i.e. size of underlying array)
int n; // size of this myvec
// Increases the capacity of the underlying array to be sz. If sz
// is smaller than the current capacity then nothing is done.
void increase_capacity(int sz) {
if (sz <= capacity) return;
double* new_arr = new double[sz]; // allocate a new array on the free store
for(int i = 0; i < capacity; ++i) { // copy old vector into new one
new_arr[i] = arr[i];
}
capacity = sz; // set the new capacity
delete[] arr; // delete the old vector
arr = new_arr;
}
public:
// create an empty vector
myvec() : capacity(10), n(0) {
arr = new double[capacity];
}
int size() const {
return n;
}
void push_back(double x) {
if (n >= capacity) increase_capacity(2 * capacity);
arr[n] = x;
++n;
}
void set(int i, double val) {
if (i < 0 || i >= n) error("range error");
arr[i] = val;
}
double get(int i) const {
if (i < 0 || i >= n) error("range error");
return arr[i];
}
~myvec() { // destructor
delete[] arr;
}
}; // class myvec
Note a few things:
We’ve changed the constructor to be a default constructor. Initially the size of the underlying array is set to 10. There’s no deep reason for this: 10 seems like a reasonable value to start with.
The push_back function has been added. It appends x to the end of the vector, increasing its size by 1. If necessary, it also resizes the underlying array.
The increase_capacity function increases the size of the underlying array. It creates a new, larger array and then copies all the values from the old array into it. Then it deletes the old array and makes arr point to the new one.
increase_capacity is in the private section of the class because we don’t want the user of myvec to call it directly. If it is not called at the right time it can cause the performance of myvec to degrade severely.
Because of the expense of calling increase_capacity, push_back always doubles the capacity of the array. This way the size of the array grows exponentially, meaning only a few calls to it are ever needed for most vectors.
When the capacity of a myvec is greater than its size, it uses more memory than is strictly required to store all the array elements. This is a compromise: using this extra memory is what gives us good performance in cases where push_back doesn’t call increase_capacity.
If memory usage is a major concern, then we could add functions to help control memory usage (perhaps at the cost of decreased speed). The C++ standard vector provides a number of such functions. If even those functions don’t meet your memory needs, then you can always revert to a low-level array.
Note
In practice, it can be very difficult to write programs that optimize both speed and memory at the same time. Very fast programs often achieve their speed by using a lot of extra memory, while very memory-efficient programs are often relatively slow. Part of the job of a programmer is to decide how and when to make such trade-offs.
The push_back function appends an item to the end of a vector. Here, lets see how to insert an item at any given location. For the sake of concreteness suppose our vector is this:
{6, 2, 1, 4, 3}
And suppose want to insert -5 at index location 2 so that, after the insertion, it looks like this:
{6, 2, -5, 1, 4, 3}
The size of the vector increases by 1, and the location of each element after the insertion point is moved up by one. The earlier in the vector an item is inserted, the more elements that must be moved up.
Here is an implementation of insert:
// Pre: 0 <= i <= n
// Post: x is at location i, and all previous elements from i
// onwards have been shifted to the right one position; the size of
// the vector is 1 larger than before calling insert
void insert(double x, int i) {
if (i < 0 || i > n) error("range error"); // x can be inserted at location n,
// i.e. the very end of the vector
push_back(0); // increase the size of the vector by 1
// move all elements from i to end of vector up one position; note
// that we must start at the right end of the vector to do this
// correctly
for(int j = n - 1; j > i; --j) {
arr[j] = arr[j - 1];
}
// put x into the vector
arr[i] = x;
}
Note the following:
Legal insertions positions are 0 up to, and including, location n, i.e. the element after the last element of the vector.
The push_back function is used to increase the size of the array. It appends 0 to the end for no other reason than some value needs to pushed. It gets over-written in the next step.
The for-loop for moving all the elements of the array from the insertion point onwards up one position is a bit tricky. It needs to work from right to left to avoid over-writing elements.
As always, tricky code should be carefully tested to make sure it works correctly. It’s especially important to test it on extreme cases, such as empty vectors, or insertions at the beginning/end of the vector.
Accessing a vector using set and get is not as convenient as using the []-bracket notation. So C++ lets you use []-brackets as follows:
class myvec {
// ...
public:
// ...
void set(int i, double val) {
if (i < 0 || i >= n) error("range error");
arr[i] = val;
}
double get(int i) {
if (i < 0 || i >= n) error("range error");
return arr[i];
}
// operator[] must return a reference to a double (instead of just a
// regular double) in order to work properly with assignment, e.g.
//
// v[5] = 4;
//
// Since v[5] is on the left
double& operator[](int i) {
if (i < 0 || i >= n) error("range error");
return arr[i];
}
const double& operator[](int i) const {
if (i < 0 || i >= n) error("range error");
return arr[i];
}
// ...
}; // class myvec
Overloading operator[] is a bit tricky: it needs to return a reference to a double, and not just a plain double. That’s necessary for myvec to work in cases like this:
v[5] = 6;
Since v[5] is on the left-hand side of =, it means we want 6 to be put into that location of the myvec. If v[5] returned a double, that couldn’t work. But returning a double reference does the trick: v[5] is just another name for the double at location 5 of v, which lets us assign to it.
We also need a const version of operator[] so it works correctly with constant myvec objects.
While operator overloading is a nice feature of C++, it is relatively complex because different operators have different rules for how they need to be overloaded correctly: you pretty much need a check-list of points to consider for each different operator.