Case Study: Creating Your Own Vector Class ========================================== 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. Dynamic Memory: Using the Free Store ------------------------------------ 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, where global data is stored. The amount of static memory a program has is set at compile-time and does not change while the program is running. - Stack memory, where local variables and function-related information is stored. Stack memory is managed automatically, i.e. it allocates and de-allocates itself according to code blocks in your program. - Free store memory, where all the other memory is put. Static memory and stack memory alone is enough for some programs, but not all. Any program that uses, for example, arbitrary sized ``vector``\ s or ``string``\ s need to use the free store. The issue is that the amount of memory objects like ``vector``\ s and ``string``\ s need is both unpredictable and not known until the program runs. The free store is accessed using ``new`` and ``delete``: - ``new`` and ``new []`` *allocate* memory on the free store. That is, they request memory from the free store. - ``delete`` and ``delete []`` *de-allocate* memory on the free store. That is, they tell the free store that previously allocated free-store memory is now free to be allocated in the future. 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. Basic Use of Pointers --------------------- 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: - ``double*`` is the type pointer to ``double`` - ``char*`` is the type pointer to ``char`` - ``string*`` is the type pointer to ``string`` - ``vector*`` is the type pointer to ``vector`` - ``double**`` is type the pointer to ``double*`` (i.e. a pointer to a pointer) - ``vector`` is the type ``vector`` of ``double*`` (i.e. a ``vector`` of pointers) - ``vector*`` is the type pointer to a ``vector`` of ``double*`` (i.e. a pointer to a ``vector`` of pointers) 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. Creating Arrays with new [] --------------------------- 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 ``int``\ s 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. Using delete [] --------------- 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: - call the correct form of delete, i.e. ``delete[]`` on memory allocated using ``new[]``, and ``delete`` on memory allocated with ``new``; - make sure they never delete the same free store memory more than once; - remember to delete free store memory at all. 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. Using a Class to Manage Arrays ------------------------------ 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: - ``myvec`` has two private variables (recall that a ``class`` uses ``private`` by default), ``arr`` and ``n``. Since they are ``private`` code outside of ``myvec`` cannot read or write them. - ``myvec`` has one constructor that takes in the size of the array. It uses an initialization list to initialize its ``private`` variables, and then in the body uses a loop to set each array location to 0. - ``set`` and ``get`` read and write values of ``myvec``. The indexing works the same as for standard C++ arrays and vectors. - ``size`` and ``get`` are declared ``const`` because they don't modify ``myvec``\ s variables in any way, and so can be used with a constant ``myvec``. - The destructor calls ``delete []`` on ``arr``, i.e. it de-allocates the memory used by ``arr``. Recall that destructors are called automatically when an object is destroyed, i.e. it goes out of scope or is deleted. Thus ``delete []`` is only called when the data is no longer needed by the program. Furthermore, the correct form of delete is called (i.e. ``delete []``, and not ``delete``), and it is only called once. 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. Range Checking -------------- 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. Adding a push_back Function --------------------------- 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: - Create a new array that is bigger than the old array. - Copy all the elements from the old array into the new array. - Delete the old array. 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. Inserting at Any Location ------------------------- 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. Overloading operator-[] ----------------------- 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.