COMS W4995 C++ Deep Dive for C Programmers
Dynamically Growable Array
In this chapter, we will be studying the implementation of a dynamically
growable integer array, IntArray. We will keep iterating on this design. We
will cover move semantics in the next chapter, and class templates in the
chapter after that. At the end, we’ll arive at the Vec class template, which
is a simplified version of the std::vector class template, a dynamically
growable array of any time.
IntArray class overview
We’ve implemented the IntArray class and a simple test driver for it in
intarray1.cpp. It’s basically an array that you can keep appending to:
class IntArray {
public:
IntArray() { // FIXME: use member initializer list
sz = 0;
cap = 1;
a = new int[cap];
}
~IntArray() {
delete[] a;
}
...
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) { ... }
private:
int* a; // FIXME: is this the right order of declarations?
size_t sz;
size_t cap;
};
Growing the array
The push_back() member function appends an integer to the end of the array.
We’ll study its implementation in a bit. The class also provides operator[]()
to access the integers in the array and two accessor member functions: size()
and capacity(). The sz member tracks how many integers are in the array
while cap tracks how large the underlying array is. cap can be larger than
sz, which means that there are empty slots at the end of the underlying array.
We left a couple of FIXMEs about the class members – we’ll revisit these
shortly. push_back() will write into those empty slots until we run out of
space, at which point the underlying array is reallocated to be larger.
Take for example the following code snippet:
IntArray ia;
ia.push_back(100);
ia.push_back(200);
ia.push_back(300);
When we declare ia, its constructor is invoked and sets up an empty array with
cap = 1. This means that space for 1 integer is allocated on the heap for a
to point to, but sz is still 0, as shown below:
When we invoke ia.push_back(100), the implementation gets to write directly
into that empty slot. As you can see below, the memory layout of the IntArray
stays the same, but there are no more empty slots:
When we invoke ia.push_back(200), the implementation sees that the array is
full. It allocates a new array with double the capacity of the old one, copies
over the old element, and then writes in the new element 200. The IntArray’s
new memory layout is shown below:
Finally, we invoke ia.push_back(300). The array is once again full, so a new
array is allocated with double the capacity, the two old elements are copied
over, and we write in the new element 300. This time, we see that cap is 4
while sz is 3. The next push_back() operation will get to write into the
empty slot:
The main() function invokes push_back() 20 times, printing out the
IntArray using our implementation of operator<<(), which simply prints each
element in the array and the capacity of the array at the time:
std::ostream& operator<<(std::ostream& os, const IntArray& ia) {
for (size_t i = 0; i < ia.size(); i++) {
os << ia[i] << " ";
}
os << "(cap=" << ia.capacity() << ")";
return os;
}
When we run the intarray1 program, we can see the underlying array doubling in
capacity everytime push_back() is called when sz == cap.
$ ./intarray1
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)
Time Complexity Analysis
The runtime cost of the push_back() member function depends on the size and
capacity of the underlying array. If the array still has empty slots, the
runtime cost is simply O(1). If the array is at capacity, we’ll have to
allocate a bigger array and copy over the existing elements first, which is an
O(N) operation.
Instead of thinking about the worse case cost, O(N), we can think about the
average cost of push_back(). Say that an IntArray that has N objects
already is at capacity and then we decide to append N more objects. The total
runtime cost will be O(N) + N * O(1) for the reallocation and copying (O(N))
plus N quick push_back() calls, each O(1). That’s 2 * O(N), which is
still just O(N). That’s O(N) / N = O(1) per push_back() call on average.
Therefore, push_back() has an amortized O(1) runtime cost. This is also
the case for the real std::vector::push_back().
Code Walkthrough
Constructor and Destructor
The constructor and destructor for IntArray are straightforward:
IntArray() {
sz = 0; // FIXME: use member initializer list
cap = 1;
a = new int[cap];
}
~IntArray() {
delete[] a;
}
The constructor allocates an integer array a of size 1 on the heap, reflecting
the initial cap of 1. sz is set to 0 because the array is initially empty.
Note the FIXME in the constructor; we’ll show a better to initialize class
members in a bit.
The destructor, as per the RAII paradigm, releases the heap-allocated integer
array a. This is pretty much what we saw with the MyString class a couple of
chapters ago.
Copy Constructor and Assignment
Here’s where we deviate from MyString – we’ve decided to delete copy
construction and assignment for IntArray. We do this by writing = delete
next to the prototype for these member functions:
IntArray(const IntArray&) = delete;
IntArray& operator=(const IntArray&) = delete;
Since these member functions are deleted, any code that tries to copy IntArray
will fail to compile. The compiler will not generate the default shallow copy
operations here because we explicity deleted the operations. Deleting copy is
actually not an unreasonable thing to do here. Imagine a huge IntArray with
hundreds or thousands of elements – it would be incredibly expensive to copy it
around. In the next chapter, we’ll introduce move operations, which allow us to
move around the underlying resources of an object without making wasteful
copies.
While we’re introducing this = delete syntax, here’s how to explicity request
the compiler-generated versions of copy constructor and assignment for your
reference:
IntArray(const IntArray&) = default;
IntArray& operator=(const IntArray&) = default;
We previously mentioned that the compiler would generate these operations for
you if you don’t explicity define them. With the introduction of move operations
in the next chapter, there will be cases where the compiler won’t generate them
for you unless you explicitly request them by writing default. More on that
later.
push_back()
The push_back() member function is implemented as follows:
void push_back(int x) {
if (sz == cap) {
int* a2 = new int[cap *= 2]; // FIXME: strong exception guarantee
std::copy(a, a+sz, a2);
delete[] a;
a = a2;
}
a[sz++] = x;
}
As we discussed earlier, if we’re not at capacity yet, we can just write into
the next open slot at sz++. Recall postfix incrementation from C: it
increments the variable, but the value of the expression is the original value
before incrementing.
If we are at capacity, we heap-allocate a new array a2 with size cap *= 2.
This is another C-style expression where we exploit the fact that the value of
the expression cap *= 2 is the new value of cap after being doubled.
After that, we copy over the array elements from a into a2. Instead of
writing the loop ourselves, we call std::copy(). The first two arguments
specify a source range that we should copy from. In this case, we pass a pointer
to the beginning of a and a pointer to one past the last element of a,
a + sz. This forms a half-open interval, [a, a+sz), from which we should
copy. We’ll revisit this paradigm of specifying ranges using half-open
intervals in a few chapters. The third argument is a pointer to the beginning of
the destination to which std::copy() should write the elements.
Strong Exception Guarantee
We left a FIXME in the implementation of push_back() that mentions a “strong
exception guarantee”. In C++, there’s varying degrees of
guarantees made
about the program state with respect to exceptions being thrown. One of them is
the strong exception guarantee, which says that if an exception is thrown in
a piece of code, the program state will be as if that code never ran.
Does our original implementation of push_back() provide a strong exception
guarantee? Recall that new will throw an exception if it couldn’t allocate
memory. Unfortunately, our cap *= 2 trick is problematic in this case. If an
exception is thrown because of new, the IntArray will now have an incorrect
capacity since we updated cap before knowing if new will succeed.
To remedy this, we just break apart the two operations:
...
int* a2 = new int[cap * 2];
cap *= 2;
...
We allocate the new array with cap * 2 and then update the cap member. This
isn’t as succinct as our original code, but it’s a lot safer. One has to be
careful when writing library code and carefully consider what kind of safety
guarantees can be offered to the user. The real std::vector::push_back()
offers the strong exception guarantee.
Member Initializer List
Let’s go back to the IntArray constructor. We initialize the three members of
the class in the body of the constructor:
IntArray() {
sz = 0 // FIXME: use member initializer list;
cap = 1;
a = new int[cap];
}
This is not the best way to initialize the members. C++ will actually default construct all members by the time we enter the body of the constructor. It doesn’t matter in this case since all of our members are primitive types and don’t have constructors, but consider what would happen if you did have some class type members with expensive constructors. It would be wasteful to have a class type member default constructed only for us to reassign it in the body of the constructor. Instead, we can provide a member initializer list that specifies how to initialize the members before entering the body of the constructor:
IntArray() : sz{0}, cap{1}, a{new int[cap]} {}
Since there’s nothing left to do in the body of the constructor, we just leave it empty. If we rewrite the constructor using the member initializer list shown above and recompile, we get a bunch of warnings:
intarray1.cpp: In constructor ‘IntArray::IntArray()’:
intarray1.cpp: warning: ‘IntArray::cap’ will be initialized after [-Wreorder]
| size_t cap;
| ^~~
intarray1.cpp: warning: ‘int* IntArray::a’ [-Wreorder]
| int* a; // FIXME: is this the right order of declarations?
| ^
intarray1.cpp: warning: when initialized here [-Wreorder]
| IntArray() : sz{0}, cap{1}, a{new int[cap]} {}
| ^~~~~~~~
intarray1.cpp: In constructor ‘IntArray::IntArray()’:
intarray1.cpp: warning: ‘*this.IntArray::cap’ is used uninitialized [-Wuninitialized]
| IntArray() : sz{0}, cap{1}, a{new int[cap]} {}
| ^~~
The compiler is warning us because we were inconsistent with the order in which we listed the members. Recall from our class definition we had the following:
class IntArray {
public:
...
private:
int* a; // FIXME: is this the right order of declarations?
size_t sz;
size_t cap;
};
Yet, our member initializer list orders them as sz, cap, a. The compiler
will initialize the members in the order in which we declared them, not the
order of the member initializer list. This is problematic because it means a
gets initialized before cap. The expression new int[cap] will end up
allocating an undefined number of integers because cap isn’t initialized yet!
We need to be careful with the order in which we declare members and that the
initializer list is in the same order. In this case, we need to ensure that
cap is initialized before a, so we rewrite the declaration order as follows:
class IntArray {
public:
...
private:
size_t sz;
size_t cap;
int* a;
};
Last updated: 2025-09-05