COMS W4995 C++ Deep Dive for C Programmers

Vec Class Template

We’re now going to turn our IntArray class into a class template so that it can be used for any data type. Our new Vec class template will be a simplified version of std::vector, but it will help us understand the value semantics of C++ standard library containers.

Class Template

Let’s turn our IntArray class into a class template named Vec. Here’s the IntArray class definition we were working with last chapter:

class IntArray {
public:
    IntArray() : sz{0}, cap{1}, a{new int[cap]} {}
    ~IntArray() { delete[] a; }

    IntArray(const IntArray&) = delete;
    IntArray& operator=(const IntArray&) = delete;

    IntArray(IntArray&& tmp) : sz{tmp.sz}, cap{tmp.cap}, a{tmp.a} {
        tmp.sz = tmp.cap = 0;
        tmp.a = nullptr;
    }

    IntArray& operator=(IntArray&& tmp) {
        if (this != &tmp) {
            delete[] a;

            sz = tmp.sz;
            cap = tmp.cap;
            a = tmp.a;

            tmp.sz = tmp.cap = 0;
            tmp.a = nullptr;
        }
        return *this;
    }

    int& operator[](int i) { return a[i]; }
    const int& operator[](int i) const { return a[i]; }

    size_t size() const { return sz; }
    size_t capacity() const { return cap; }

    void push_back(int x) {
        if (sz == cap) {
            int* a2 = new int[cap * 2];
            cap *= 2;
            std::copy(a, a+sz, a2);
            delete[] a;
            a = a2;
        }
        a[sz++] = x;
    }

private:
    size_t sz;
    size_t cap;
    int* a;
};

We start by changing the element type int to a generic template type parameter T:

template <typename T>
class Vec {
public:
    ...
private:
    size_t sz;
    size_t cap;
    T* a;
};

The types of sz and cap are still size_t, but a is now of type T* instead of int*. a points to the underlying array type T elements now.

Second, we port over the Essential-6 member functions. The only difference is that the constructor now invokes new T[cap] instead of new int[cap]. The constructor allocates an array of cap elements of type T on the heap.

template <typename T>
class Vec {
public:
    Vec() : sz{0}, cap{1}, a{new T[cap]} {}
    ~Vec() { delete[] a; }

    Vec(const Vec&) = delete;
    Vec& operator=(const Vec&) = delete;

    Vec(Vec&& tmp) : sz{tmp.sz}, cap{tmp.cap}, a{tmp.a} {
        tmp.sz = tmp.cap = 0;
        tmp.a = nullptr;
    }

    Vec& operator=(Vec&& tmp) {
        if (this != &tmp) {
            delete[] a;

            sz = tmp.sz;
            cap = tmp.cap;
            a = tmp.a;

            tmp.sz = tmp.cap = 0;
            tmp.a = nullptr;
        }
        return *this;
    }
    ...
private:
    size_t sz;
    size_t cap;
    T* a;
};

Third, we copy over the rest of the IntArray member functions:

template <typename T>
class Vec {
public:
    Vec() : sz{0}, cap{1}, a{new T[cap]} {}
    ~Vec() { delete[] a; }

    Vec(const Vec&) = delete;
    Vec& operator=(const Vec&) = delete;

    Vec(Vec&& tmp) : sz{tmp.sz}, cap{tmp.cap}, a{tmp.a} {
        tmp.sz = tmp.cap = 0;
        tmp.a = nullptr;
    }

    Vec& operator=(Vec&& tmp) {
        if (this != &tmp) {
            delete[] a;

            sz = tmp.sz;
            cap = tmp.cap;
            a = tmp.a;

            tmp.sz = tmp.cap = 0;
            tmp.a = nullptr;
        }
        return *this;
    }

    T& operator[](int i) { return a[i]; }
    const T& operator[](int i) const { return a[i]; }
    size_t size() const { return sz; }
    size_t capacity() const { return cap; }

    void push_back(const T& x) {
        if (sz == cap) {
            T* a2 = new T[cap * 2];
            cap *= 2;
            std::copy(a, a+sz, a2);
            delete[] a;
            a = a2;
        }
        a[sz++] = x;
    }
private:
    size_t sz;
    size_t cap;
    T* a;
};

We’ve adjusted the return types of operator[]() to be T& and const T& instead of int and int&, respectively. size() and capacity() are unchanged.

We did, however, make two changes to push_back(). Like we saw in the constructor, the array-new statement was changed from new int[cap * 2] to new T[cap * 2]. The other change is the type of the argument x. IntArray simply had int x, whereas Vec has const T& x. It would have been overkill to specify const int& for IntArray::push_back() because int is a primitive type that is cheap to copy. Given that Vec may potentially store large objects, it’d be wasteful to copy the argument x only for us to copy it again in the assignment a[sz++] = x, so we take the argument by const reference.

Finally, we complete our class definition by porting over the put-to operator overload:

template <typename T>
class Vec {
    ...
};

template <typename T>
std::ostream& operator<<(std::ostream& os, const Vec<T>& vec) {
    for (size_t i = 0; i < vec.size(); i++) {
        os << vec[i] << " ";
    }
    std::cout << "(cap=" << vec.capacity() << ")" << std::flush;
    return os;
}

Unlike the IntArray overload, this operator<<() overload is a function template. The template type parameter is the element type of Vec, which is T. Note that the second parameter’s type is Vec<T>, not just Vec. By itself, Vec is not an actual class – it’s just a class template.

We’re now ready to use our brand new Vec class template! Let’s port our old createIntArray() function into the following two new functions:

/*
IntArray createIntArray() {
    IntArray tmp;
    for (int i = 0; i < 20; i++) {
        tmp.push_back(i);
        std::cout << tmp << std::endl;
    }
    return tmp;
}
*/

Vec<int> createIntVec() {
    Vec<int> tmp;
    for (int i = 0; i < 20; i++) {
        tmp.push_back(i);
        std::cout << tmp << std::endl;
    }
    return tmp;
}

Vec<std::string> createStrVec() {
    Vec<std::string> tmp;
    for (char c = 'A'; c <= 'Z'; c++) {
        std::string s;
        s += c;
        tmp.push_back(s);
        std::cout << tmp << std::endl;
    }
    return tmp;
}

createIntVec() and createStrVec() return concrete instantiations of our Vec class template with int and std::string, respectively.

To verify that Vec<int> and Vec<std::string> work as expected, we call createIntVec() and createStrVec() from the main() function:

int main() {
    using namespace std;

    Vec<int> iv { createIntVec() };

    Vec<string> sv { createStrVec() };
}

Here’s the program output for 07/vec1:

0 (cap=1)
0 1 (cap=2)
0 1 2 (cap=4)
0 1 2 3 (cap=4)
0 1 2 3 4 (cap=8)
0 1 2 3 4 5 (cap=8)
0 1 2 3 4 5 6 (cap=8)
0 1 2 3 4 5 6 7 (cap=8)
0 1 2 3 4 5 6 7 8 (cap=16)
0 1 2 3 4 5 6 7 8 9 (cap=16)
0 1 2 3 4 5 6 7 8 9 10 (cap=16)
0 1 2 3 4 5 6 7 8 9 10 11 (cap=16)
0 1 2 3 4 5 6 7 8 9 10 11 12 (cap=16)
0 1 2 3 4 5 6 7 8 9 10 11 12 13 (cap=16)
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 (cap=16)
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 (cap=16)
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 (cap=32)
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 (cap=32)
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 (cap=32)
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 (cap=32)
A (cap=1)
A B (cap=2)
A B C (cap=4)
A B C D (cap=4)
A B C D E (cap=8)
A B C D E F (cap=8)
A B C D E F G (cap=8)
A B C D E F G H (cap=8)
A B C D E F G H I (cap=16)
A B C D E F G H I J (cap=16)
A B C D E F G H I J K (cap=16)
A B C D E F G H I J K L (cap=16)
A B C D E F G H I J K L M (cap=16)
A B C D E F G H I J K L M N (cap=16)
A B C D E F G H I J K L M N O (cap=16)
A B C D E F G H I J K L M N O P (cap=16)
A B C D E F G H I J K L M N O P Q (cap=32)
A B C D E F G H I J K L M N O P Q R (cap=32)
A B C D E F G H I J K L M N O P Q R S (cap=32)
A B C D E F G H I J K L M N O P Q R S T (cap=32)
A B C D E F G H I J K L M N O P Q R S T U (cap=32)
A B C D E F G H I J K L M N O P Q R S T U V (cap=32)
A B C D E F G H I J K L M N O P Q R S T U V W (cap=32)
A B C D E F G H I J K L M N O P Q R S T U V W X (cap=32)
A B C D E F G H I J K L M N O P Q R S T U V W X Y (cap=32)
A B C D E F G H I J K L M N O P Q R S T U V W X Y Z (cap=32)

STL Value Semantics

std::vector and other containers in the C++ standard library are often referred to as STL (Standard Template Library) containers. We’ll study them in more detail in a few chapters from now.

Our Vec class template is a simplified version of std::vector. One thing that Vec has in common with std::vector and other STL containers is its value semantics, i.e., the fact that it stores its elements by value, not by reference. In other words, Vec completely owns its underlying elements.

Let’s study the lifetime of Vec elements by considering the program 07/vec2. It has the same class template definition of Vec that we saw in 07/vec1, but we replaced the main() function with the following:

int main() {
    Vec<MyString> v;    // (1)
    v.push_back("abc"); // (2)
    v.push_back("def"); // (3)
    MyString s{"xyz"};  // (4)
    v.push_back(s);     // (5)
}

In line 1, we declare a Vec<MyString> v on the stack. The Vec constructor shown below will heap-allocate a MyString array of size 1:

Vec() : sz{0}, cap{1}, a{new T[cap]} {}

Since we don’t provide an initializer list in the array-new statement, the single MyString object will be default-constructed. Recall that our MyString default constructor allocates 1 byte on the heap representing an empty string. With all of that in mind, the memory layout after line 1 will look like this:

07-vec-1

On line 2, we invoke Vec::push_back() with the string literal "abc". We previously discussed that the compiler will promote a string literal to a MyString object using the MyString constructor that takes a const char*. The compiler will create a temporary object from the string literal "abc" and passes it to push_back() as the x parameter.

Since there’s room in the underlying array (sz == 0 and cap == 1), we just assign x into the next empty slot with a[sz++] = x. Here, we are invoking the MyString copy assignment operator on a[0]. The temporay unnamed MyString{"abc"} object will be destructed when push_back() returns. After line 2, the memory layout will look like this:

07-vec-2

On line 3, we invoke push_back() again with another string literal "def". Just like before, a temporary unnamed MyString object is created and passed into push_back().

At this point, however, sz == cap == 1, so the underlying array needs to get reallocated with twice the capacity. The Vec implementation allocates a new MyString array with size 2. The array-new statement new T[cap * 2] default-constructs each MyString element in the new array. We then copy over the element from the old array into the newly allocated array using std::copy() library function before deleting the old array. The memory layout looks like this now:

07-vec-3

When we created the new array, two MyString objects were default-constructed inside of it. Our call to std::copy() to copy over the element from the old array invoked the copy assignment operator on a[0]. a[1] is still a default-constructed empty MyString object. We note that this is not how the real std::vector implementation works. We’ll revisit this point shortly.

At last, we copy assign the temporary MyString{"def"} object to a[1]. After line 3 is completed, the memory layout will look like this:

07-vec-4

On line 4, we create a named MyString object s from the string literal "xyz" on the stack, which we push_back() into v on line 5. v is once again at capacity, so its capacity is doubled to 4, the two elements in the old underlying array are copied over, and s is copy-assigned into a[2]. The final memory layout is shown below:

07-vec-5

Placement New

Every time we reallocate the underlying array in Vec, we use the array-new syntax. We showed above that this will default-construct every element in the new array. When we push_back() into Vec, we copy-assign the value into the array. It’s wasteful that each element of the array is default-constructed only for us to overwrite it with a new string when we invoke push_back().

The real std::vector performs array reallocation in a more efficient way. Instead of using new[], it decouples memory allocation from object construction. It first allocates raw, untyped memory for its underlying array. (You can imagine it’s invoking malloc(sizeof(MyString) * cap), even though the actual mechanism may be different.) As we’ve discussed before, allocating raw memory like this won’t perform any constructions. The push_back() implementation will then construct the new object directly into that raw memory, avoiding the wasteful copy assignment.

The C++ placement new syntax allows us to decouple memory allocation from object construction. In the example below, we create a char array on the stack with sizeof(MyString) bytes, which is exactly the amount of space we’d need to construct a MyString object. We can construct a MyString into that buffer using placement new syntax, which takes the memory address of that buffer. The placement new statement returns that same memory address as a MyString*.

// For brevity, we omit the proper memory alignment directive for MyString.
char s_buf[sizeof(MyString)];
MyString* sp = new (s_buf) MyString{"hello"};

Since placement new didn’t include memory allocation, it’d be incorrect to invoke delete sp since that would try to deallocate the underlying memory. In order to destruct the object without deallocating the underlying memory, we must invoke the destructor manually:

char s_buf[sizeof(MyString)];
MyString* sp = new (s_buf) MyString{"hello"};
...
sp->~MyString();

Strong Exception Guarantee Revisited

Recall that the IntArray::push_back() had the strong exception guarantee:

void push_back(int x) {
    if (sz == cap) {
        int* a2 = new int[cap * 2];
        cap *= 2;
        std::copy(a, a+sz, a2);
        delete[] a;
        a = a2;
    }
    a[sz++] = x;
}

If an exception was thrown somewhere in push_back(), the implementation guaranteed that the state of IntArray would be as if push_back() was never called. In this case, the call to new[] was the only thing that could throw an exception. No additional handling was needed since no state was modified before calling new[].

When we ported push_back() to the Vec class template, the implementation lost its strong exception guarantee. Below is the ported version:

void push_back(const T& x) {
    if (sz == cap) {
        T* a2 = new T[cap * 2];
        cap *= 2;
        std::copy(a, a+sz, a2);
        delete[] a;
        a = a2;
    }
    a[sz++] = x;
}

std::copy is a function template that handles copying for any type T. int was trivially copiable, but we don’t know what copy looks like for an arbitrary type T. The copy operation for T could very well throw an exception. The assignment a[sz++] = x could also throw an exception (we also don’t know what copy assignment looks like for an arbitrary type T), in which case sz is erroneously incremented. In order to restore the strong exception guarantee, we must handle the case where these two copy operations throw an exception. 07/vec3 redefines push_back() as follows:

void push_back(const T& x) {
    if (sz == cap) {
        T* a2 = new T[cap * 2];
        try {
            std::copy(a, a+sz, a2);
        } catch (...) {
            delete[] a2;
            throw;
        }
        cap *= 2;
        delete[] a;
        a = a2;
    }
    a[sz] = x;
    sz++;
}

We moved the cap *= 2 statement underneath the std::copy() so that the only thing we’d have to rollback if std::copy() threw an exception is the allocation of a2. We catch any exception thrown by std::copy, delete a2, and then rethrow that same exception. We also moved sz++ into a separate statement after the copy assignment so we don’t increment sz unless copy assignment succeeds. Even then, our solution isn’t perfect. Our decision to have Vec default-construct empty slots and then copy-assign into them (instead of using placement new like std::vector) makes it tricky to correctly implement the strong exception guarantee. As such, we make the simplifying assumption that, if copy assignment operator throws an exception, it’ll still leave the slot with a valid default-constructed object.

Note that our Vec class template always copies over the elements when performing reallocation. You can imagine that it’d be more efficient if the elements were moved instead. std::vector does in fact try to move elements during reallocation, but with a caveat.

std::vector::push_back() wants to provide the strong exception guarantee if possible. If reallocation copies over the old elements, it’s easy to roll back that operation because copy does not modify the original elements, as we saw in our implementation above. Moving the old elements, on the other hand, may not be easy to roll back if one of the move operations throws an exception because move modifies the original element.

Prioritizing the strong exception guarantee, std::vector chooses between move and copy for reallocation as follows:

  1. The element will be moved if the element type has a move constructor that is marked noexcept, indicating that the move constructor will not throw any exceptions.
  2. If the element type does not have a noexcept move constructor, the element will be copied. std::vector doesn’t choose a move constructor that could potentially throw an exception because it prioritizes the strong exception guarantee over efficiency.
  3. If the element type doesn’t have a copy constructor, then std::vector forgoes the strong exception guarantee and falls back to the potentially throwing move constructor.

Last updated: 2025-09-18