19. Vector, Templates, and Exceptions

We could just allocate a new array every single time someone calls push_back(): but that is not very efficient! Better to allocate some extra memory for every chunk we use, like this:

class vector {
    int sz;
    double* elem;
    int space;  // number of elems + free space
public:
    // ...
};
                            

Here's what our key method, reserve, looks like:

void vector::reserve(int newalloc)
{
    if(newalloc <= space) return;
    double* p = new double[newalloc];
    for(int i = 0; i < sz; ++i) p[i] = elem[i];  // copy elements
    delete[] elem;  // deallocate old space
    elem = p;
    space = newalloc;
}
                            

We need to handle the following cases:

• The new size is larger than the old allocation.
• The new size is larger than the old size, but smaller than or equal to the old allocation.
• The new size is equal to the old size.
• The new size is smaller than the old size.

resize() is actually very simple, given we've written reserve():

void vector::resize(int newsize)
{
    reserve(newsize);
    for(int i = sz; i < newsize; ++i) elem[i] = 0;
    sz = newsize;
}
                            

Can you verify we handle all of these cases correctly?

What do we do when we run out of space? Interestingly, most implementations of vector ask for double the amount of space the vector is already using. (The Lindy effect!) Here is the code for push_back():

void vector::push_back(double d)
    // increase vector size by one and initialize with d 
{
    if(space == 0) reserve(8);
    else if(sz == space) reserve(2*space);
    elem[sz] = d;  // put d at the end 
    ++sz;  // increase the size 
}
                            

Assignment copies the elements to the new vector, but does not worry about the extra space: maybe the new vector won't need it! The code:

vector& vector::operator=(const vector& a)
{
    if(this == &a) return *this;  // self-assignment! 

    if(a.sz <= space) { // enough space! 
// so just copy  
        for(int i = 0; i < a.sz; ++i) p[i] = a.elem[i];
        sz = a.sz;
        return *this;
    }
}
                            

See our textbook for source code here.

We achieve that goal like this:

template<class T> class vector {
// implementation of vectors follows here
}
                            

One way to think of this is that the compiler uses the template and the type we give it to generate the proper code for that type, so that each element of a vector of char takes up 1 byte, and each element of a vector of int takes up 4 bytes.

For member functions, the compiler generates code to handle the appropriate type. So if our template has:

void push_back(const T& d);
                            

Then for our Token vector in Token_stream we get:

void push_back(const Token& d);
                            

"Generic programming: Writing code that works on a variety of types presented as arguments, as long as those argument types meet spcific syntatctic and semantic requirements." (p. 682)

Polymorphism means the "programmer presents many versions of a concept using a single interface." (p. 682) Generic programming relies on types offered at compile time, while object-oriented programming relies on class hierarchies and virtual functions. Templates resolve the concrete method to call at compile time (making them faster), while object-oriented programming resolves the concrete method to use at run-time, making it more flexible.

C++ 14 supports concepts, which can be used to characterize what types can fill in the T slot in a template. A few examples:

• Element can be an element in a container.
• Container can hold elements.
• Forward_iterator supports traversing a sequence, such as a linked list, a vector, or an array.

Thus we can write:

template<Element T> class vector { /* */ };
                            

Templates do not support putting a subclass of a type T in a container expecting the parent type.

Interesting but beyond what we can cover.

Interesting but beyond what we can cover.

Interesting but beyond what we can cover.

1. a; 2. b; 3. b; 4. c; 5. a; 6. c;