How to implement a vector in C

Vectors, or dynamic arrays, are fundamental data structures in programming. They allow us to store and manipulate collections of data efficiently. While C doesn’t have built-in support for vectors like some other languages, we can implement our own.

Understand vectors

A vector is a dynamic array that can grow or shrink as needed, making it an ideal choice for managing lists of items. This dynamic resizing sets vectors apart from traditional C arrays, which have a fixed size.

Below is an illustration of some staple methods that can be performed on a vector:

// Function to add an element to the vector (push_back)
void push_back(Vector* vector, int value) {
    if (vector->data == NULL) {
        // If the vector is empty, allocate memory for one element
        vector->data = (int*)malloc(sizeof(int));
        vector->capacity = 1;
    } 
    else if (vector->size >= vector->capacity) {
        // If the vector is full, double its capacity by reallocating memory
        vector->capacity *= 2;
        vector->data = (int*)realloc(vector->data, vector->capacity * sizeof(int));
    }
    // Add the new element to the end of the vector and increment the size
    vector->data[vector->size] = value;
    vector->size++;
}

#include <stdio.h>
#include <stdlib.h>
// Define a structure to represent a vector
typedef struct {
    int* data;      // Pointer to the array of data
    size_t size;    // Current number of elements in the vector
    size_t capacity; // Total capacity of the vector
} Vector;
// Function to create a new vector
Vector* create_vector() {
    // Allocate memory for the Vector structure
    Vector* vector = (Vector*)malloc(sizeof(Vector));
    vector->data = NULL;   // Set data pointer to NULL, indicating an empty vector
    vector->size = 0;     // Initialize the size to 0 (no elements in the vector)
    vector->capacity = 0; // Initialize the capacity to 0 (no memory allocated)
    return vector; // Return the newly created vector
}
// Function to add an element to the vector (push_back)
void push_back(Vector* vector, int value) {
    if (vector->data == NULL) {
        // If the vector is empty, allocate memory for one element
        vector->data = (int*)malloc(sizeof(int));
        vector->capacity = 1;
    } 
    else if (vector->size >= vector->capacity) {
        // If the vector is full, double its capacity by reallocating memory
        vector->capacity *= 2;
        vector->data = (int*)realloc(vector->data, vector->capacity * sizeof(int));
    }
    // Add the new element to the end of the vector and increment the size
    vector->data[vector->size] = value;
    vector->size++;
}
// Function to remove the last element from the vector (pop_back)
void pop_back(Vector* vector) {
    if (vector->size > 0) {
        // If the vector is not empty, decrement the size to remove the last element
        vector->size--;
    }
}
// Function to access an element at a specific index (vector_at)
int vector_at(Vector* vector, size_t index) {
    if (index >= vector->size) {
        // Check if the provided index is out of bounds
        fprintf(stderr, "Index out of bounds\n"); // Print an error message
        exit(1); // Exit the program with an error code
    }
    return vector->data[index]; // Return the element at the specified index
}
// Function to get the current size of the vector
size_t size(Vector* vector) {
    return vector->size; // Return the size of the vector
}
// Function to check if the vector is empty
int is_empty(Vector* vector) {
    return vector->size == 0; // Return 1 if the vector is empty, 0 otherwise
}
// Main function
int main() {
    Vector* vector = create_vector(); // Create a new vector
    // Add elements to the vector
    push_back(vector, 10);
    push_back(vector, 20);
    push_back(vector, 30);
    // Display the size of the vector
    printf("Vector size: %zu\n", size(vector));
    // Access and print an element at a specific index
    printf("Element at index 1: %d\n", vector_at(vector, 1));
    // Remove the last element
    pop_back(vector);
    printf("Popped an element. New size: %zu\n", size(vector));
    // Check if the vector is empty and print the result
    printf("Is the vector empty? %s\n", is_empty(vector) ? "Yes" : "No");
    // Free the allocated memory to prevent memory leaks
    free(vector->data);
    free(vector);
    return 0; // Exit the program with a success code
}

Below are the properties of the Main function:

Line 68: We declare a pointer to a Vector structure called vector. It calls the create_vector function to create a new vector and assigns the returned pointer to vector.
Lines 71–73: We call the push_back function to add the values 10, 20, and 30 to the vector.
Line 76: We use the size function to determine the size of the vector and print it.
Line 79: We use the vector_at function to determine the value at index 1 and print it.
Line 82: We use the pop_back function to remove the last element of the vector.
Line 83: We use the size function to determine the size of the vector and print it.
Line 86: We use the is_empty method to determine the emptiness of the vector and print "Yes" if the vector is empty or "No" otherwise.
Line 89: We release the memory allocated for the data array inside the vector. This ensures there are no memory leaks by freeing the data before freeing the vector itself.
Line 90: Lastly, we free the memory allocated for the vector structure. It’s essential to free the vector to prevent memory leaks.

How to implement a vector in C

Understand vectors

Implement a basic vector

Set up the vector structure

Create a vector

Add an element

Remove an element

Access an element

Determine the vector’s size and check for emptiness

Test the implementation