Dynamic array implementation - C++

We discussed queue implementation in here and about vector here. Like a queue we will now discuss vector implementation in this post. A vector is a simple data structures similar to an array, but its size is dynamic. The main feature is that we can access any element in vector in O(1) time. Vector has three main methods

• size() - returns the number of elements.
• push(element) - inserts a new element at the back of the vector.
• [index] - returns the element at that index from the vector.

How hard can it be? Just think about this for a while.

What is going on with Arrays and Memory

In an array, how can we access any element in O(1) time? It’s kind of intuitive because arrays are allocated in a contiguous block of memory. We can imagine this as a box where the box size is the size of the array. For example, an int’s size is 4 bytes, so if we allocate a new array of 5 elements, then the size will be 5*4=20B. Thus, in memory, we allocate 20B. If we want to access the 3rd element of this array, we can easily find its location; it’s just the first memory location of this array plus 2*4=8B. You can see this from the image below.

Problems

Okay, we have some understanding of memory and array allocation. But now, how can we achieve a dynamically sized array like a vector? We could use multiple arrays in a chain-like structure similar to a queue. In this case, if the current array is not enough, we will create a new array and link it to the old chain. Now, how can we access any elements? If we want to access the last element of the array, we have to traverse the chain, so it’s not O(1), but we can create a dynamically sized array. If we set the chunk size to 50, and we want to store 200 numbers, we would have 4 chunks. To access the 190th element, we would first find the chunk, then traverse this chunk, and access the element from the chunk. But this is not O(1), so how?

Implementation

We can’t have chunks, right? Or we could track the chunk pointers in an array. In this idea, we could just find the chunk number, then easily find the chunk’s pointer. If we know the chunk’s pointer, we can access any element of this array. But we don’t know how many chunks we will need, so other problems will arise. Is it possible to just have one array? Yes, but how do we increase its size, which was the first problem we encountered? So, how can we increase the size of the array? We could create a new array with enough size and then copy the old array. Yes, it’s costly, but it can be efficient. So, how do we determine the new size? In this case, the new size is twice the old one, which is the efficient way. We could change this for our own purposes. Now that we have the idea, how do we implement this?

We need to declare our structure. We have an array that can store our items, size indicates how many we have used, and capacity is the size of the array.

class Vector {
private:
    int size; // size of the vector
    int capacity; // capacity of the vector
    int *arr; // our array
};

How about pushing a new element? We have to check the capacity, and if it’s sufficient, we don’t need to allocate a new array. If not, we have to allocate a new array.

void resize(int new_size) {
    int *new_p = new int[new_size]; // allocate new array 
    for(int i = 0; i < size; i++) { // copy old array
        new_p[i] = arr[i];
    }
    capacity = new_size; // update capacity
    delete[] arr; // delete old array from memory
    arr = new_p; // update our array
}

void push_back(int v) {
    if(capacity < size + 1) { // if it's not enough, we have to allocate a larger array
        resize(capacity == 0 ? 1 : capacity * 2); // the new array's size is twice the old
    }
    arr[size] = v; // set the new element
    size++; // update the size
}

Full Implementation

Here’s the full implementation of the code:

#include <iostream>
using namespace std;

class Vector {
private:
    int s, c;
    int *p;
public:
    Vector() {
        s = c = 0;
        p = nullptr;
    }
    int size() {
        return s;
    }
    int capacity() {
        return c;
    }
    bool is_empty() {
        return s == 0;
    }
    void resize(int new_size) {
        int *new_p = new int[new_size]; 
        for(int i = 0; i < s; i++) {
            new_p[i] = p[i];
        }
        c = new_size;
        delete p;
        p = new_p;
    }
    int operator[](int index) {
        return p[index];
    }
    void push_back(int v) {
        if(c < s+1) {
            resize(c == 0 ? 1 : c*2);
        }
        p[s] = v;
        s++;
    }
};

int main() {
    Vector v;
    v.push_back(1);
    cout << v.capacity() << " " << v.size() << "\n";
    v.push_back(2);
    cout << v.capacity() << " " << v.size() << "\n";

    v.push_back(3);
    cout << v.capacity() << " " << v.size() << "\n";

    v.push_back(4);
    cout << v.capacity() << " " << v.size() << "\n";

    v.push_back(5);
    cout << v.capacity() << " " << v.size() << "\n";
    
    v.push_back(5);
    cout << v.capacity() << " " << v.size() << "\n";

    cout << v[5] << endl;
    return 0;
}

Conclusion

I’ve written about the basics of vector implementation. If we look at this, push_back is not exactly O(1). So, if we know the size we need, we should resize the vector and then set the element instead of using push_back. This concept applies not just in C++, but also in other languages like Golang and others that have dynamic arrays. And now we know difference between size() and capacity(). Now we understand why. But in this implementation we have doubled the old size, but it doesn’t have to be this way.