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.
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:
In C, we can implement a vector using a structure and set of functions to manipulate it.
Here’s how we can define a basic vector structure:
#include <stdio.h>#include <stdlib.h>// Define a structure to represent a vectortypedef struct {int* data; // Pointer to the array of datasize_t size; // Current number of elements in the vectorsize_t capacity; // Total capacity of the vector} Vector;
Below are the properties of the Vector
structure:
data
: This is a pointer to the dynamically allocated array where the vector’s elements will be stored.
size
: This is the current number of elements in the vector.
capacity
: This is the total capacity of the vector, which is the maximum number of elements it can hold without resizing.
To create a new vector, we’ll define a function shown by the highlighted lines below:
// Function to create a new vectorVector* create_vector() {// Allocate memory for the Vector structureVector* vector = (Vector*)malloc(sizeof(Vector));vector->data = NULL; // Set data pointer to NULL, indicating an empty vectorvector->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}
Below are the properties of the create_vector
function:
Line 4: Allocate memory for the Vector
structure in the vector
variable.
Line 5: Initialize the data
property as 0, indicating an empty vector.
Lines 6–7: Set the size
and capacity
properties to 0
.
Line 8: Return the initialized structure.
To add elements to the vector, we’ll define a function shown by the highlighted lines below:
// 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 elementvector->data = (int*)malloc(sizeof(int));vector->capacity = 1;}else if (vector->size >= vector->capacity) {// If the vector is full, double its capacity by reallocating memoryvector->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 sizevector->data[vector->size] = value;vector->size++;}
Below are the properties of the push_back
function:
Lines 3–7: If the vector is empty, we allocate memory for one element.
Line 8–12: Otherwise, if the vector is full, we double its capacity by reallocating memory.
Line 14: Next, we add the element to the end of the vector.
Line 15: Lastly, we increment the size of the vector.
To remove the last element from the vector, we’ll define a function shown by the highlighted lines below:
// 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 elementvector->size--;}}
Below are the properties of the pop_back
function:
Lines 3–6: If the vector is non-empty, we decrement its size.
To access an element at a specific index, we’ll define a function shown by the highlighted lines below:
// 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 boundsfprintf(stderr, "Index out of bounds\n"); // Print an error messageexit(1); // Exit the program with an error code}return vector->data[index]; // Return the element at the specified index}
Below are the properties of the vector_at
function:
Line 3: We check if the provided index is within bounds.
Lines 5–6: If not, we print an error message and exit.
Line 8: If the above condition is not satisfied, we return the element at the given index.
To check the size of a vector and determine whether it’s empty, we’ll define two functions shown by the highlighted lines below:
// Function to get the current size of the vectorsize_t size(Vector* vector) {return vector->size; // Return the size of the vector}// Function to check if the vector is emptyint is_empty(Vector* vector) {return vector->size == 0; // Return 1 if the vector is empty, 0 otherwise}
Below are the properties of the size
and is_empty
functions:
Line 3: We return the current size of the vector.
Line 8: We return true if the vector is empty and false otherwise.
Now that we’ve implemented a basic vector and its functions, here’s how we can use it:
#include <stdio.h>#include <stdlib.h>// Define a structure to represent a vectortypedef struct {int* data; // Pointer to the array of datasize_t size; // Current number of elements in the vectorsize_t capacity; // Total capacity of the vector} Vector;// Function to create a new vectorVector* create_vector() {// Allocate memory for the Vector structureVector* vector = (Vector*)malloc(sizeof(Vector));vector->data = NULL; // Set data pointer to NULL, indicating an empty vectorvector->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 elementvector->data = (int*)malloc(sizeof(int));vector->capacity = 1;}else if (vector->size >= vector->capacity) {// If the vector is full, double its capacity by reallocating memoryvector->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 sizevector->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 elementvector->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 boundsfprintf(stderr, "Index out of bounds\n"); // Print an error messageexit(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 vectorsize_t size(Vector* vector) {return vector->size; // Return the size of the vector}// Function to check if the vector is emptyint is_empty(Vector* vector) {return vector->size == 0; // Return 1 if the vector is empty, 0 otherwise}// Main functionint main() {Vector* vector = create_vector(); // Create a new vector// Add elements to the vectorpush_back(vector, 10);push_back(vector, 20);push_back(vector, 30);// Display the size of the vectorprintf("Vector size: %zu\n", size(vector));// Access and print an element at a specific indexprintf("Element at index 1: %d\n", vector_at(vector, 1));// Remove the last elementpop_back(vector);printf("Popped an element. New size: %zu\n", size(vector));// Check if the vector is empty and print the resultprintf("Is the vector empty? %s\n", is_empty(vector) ? "Yes" : "No");// Free the allocated memory to prevent memory leaksfree(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.
Free Resources