How to implement a vector in C

In my previous article, I explained how to create a dynamic array in C. After reading the post, Many readers requested a guide on implementing a vector in C.

A vector is essentially a dynamic array that stores a collection of elements same type in a contiguous memory. It has the ability to resize itself automatically when an element is inserted or deleted.

A vector is essentially a dynamic array that can automatically resize itself when elements are added or removed. Unlike a linked list, where each node requires separate memory allocation, a vector stores elements in contiguous memory. This allows for fast access using an index while avoiding the overhead of per-node allocations. To manage resizing efficiently, we allocate extra memory initially and adjust it as needed.

Since C does not have built-in support for templates or vector containers like C++, we will implement a vector using structures and pointers. Our vector will store elements as void pointers (void*), making it a generic container capable of holding different data types. Now, let’s dive into the implementation!

 

Key Features of Our Vector Implementation:

I will implement the following feature in my own created C vector.

• Dynamic Resizing: The array should automatically expand when new elements are added.
• Efficient Memory Management: Implement a resizing strategy to optimize memory usage.
• Type Safety: Using void* allows storing different types, but macros can improve type safety.
• Robust Error Handling: Check for memory allocation failures and invalid operations.
• Thread Safety Considerations: Use synchronization mechanisms if needed.
• User-friendly API: Functions for adding, removing, and accessing elements.

 

Code implementation of the vector in C:

Here is the code implementation of a dynamic vector in C, structured with function pointers to emulate object-oriented behavior. You have to follow the following steps to create your version of the vector in C.

Step 1: Define the Vector Structure

We define a Vector structure to store elements dynamically and a separate vector function structure to manage function pointers.

//Store and track the stored data
typedef struct sVectorList
{
    void **items; // Stores elements (void* for flexibility)
    int capacity; // Maximum capacity
    int total;  // Current number of elements
} sVectorList;

 

// Structure containing the function pointers
typedef struct sVector vector;
struct sVector
{
    sVectorList vectorList;  /**< List to store vector elements */

    int (*pfVectorTotal)(vector *); /**< Retrieves the total number of elements in the vector */

    int (*pfVectorResize)(vector *, int); /**< Resizes the vector to a new capacity */

    int (*pfVectorAdd)(vector *, void *); /**< Adds an element to the vector */

    int (*pfVectorSet)(vector *, int, void *); /**< Sets an element at a specific index in the vector */

    void *(*pfVectorGet)(vector *, int); /**< Retrieves an element from the vector */

    int (*pfVectorDelete)(vector *, int); /**< Deletes an element from the vector */

    int (*pfVectorFree)(vector *); /**< Frees the memory allocated for the vector */
};

 

Now you need to create some macro for better readability and allocate the memory initially. You can change the macro value as per your requirement.

#define VECTOR_INIT_CAPACITY 6
#define UNDEFINE  -1
#define SUCCESS 0


#define VECTOR_INIT(vec) vector vec;\
 vector_init(&vec)

 

Step 2: Initialize the Vector:

We create a function to initialize the vector with an initial capacity and function pointers with the appropriate function.

void vector_init(vector *v)
{
    //init function pointers
    v->pfVectorTotal = vectorTotal;
    v->pfVectorResize = vectorResize;
    v->pfVectorAdd = vectorPushBack;
    v->pfVectorSet = vectorSet;
    v->pfVectorGet = vectorGet;
    v->pfVectorFree = vectorFree;
    v->pfVectorDelete = vectorDelete;
    //initialize the capacity and allocate the memory
    v->vectorList.capacity = VECTOR_INIT_CAPACITY;
    v->vectorList.total = 0;
    v->vectorList.items = malloc(sizeof(void *) * v->vectorList.capacity);

}

 

Step 3: Resize Function:

It dynamically resizes the vector when needed. This function allocates memory with a new size using the realloc library function and updates the tracking parameters. If the allocation fails, it returns an error.

int vectorResize(vector *v, int capacity)
{
    int  status = UNDEFINE;
    if(v)
    {
        void **items = realloc(v->vectorList.items, sizeof(void *) * capacity);
        if (items)
        {
            v->vectorList.items = items;
            v->vectorList.capacity = capacity;
            status = SUCCESS;
        }
    }
    return status;
}

 

Step 4: Adding Elements:

This function appends a new element to the end of the vector. If the vector reaches its capacity, it automatically resizes to accommodate the new element, ensuring efficient memory utilization.

int vectorPushBack(vector *v, void *item)
{
    int  status = UNDEFINE;
    if(v)
    {
        if (v->vectorList.capacity == v->vectorList.total)
        {
            status = vectorResize(v, v->vectorList.capacity * 2);
            if(status != UNDEFINE)
            {
                v->vectorList.items[v->vectorList.total++] = item;
            }
        }
        else
        {
            v->vectorList.items[v->vectorList.total++] = item;
            status = SUCCESS;
        }
    }
    return status;
}

 

Step 5: Set data at a given index:

The vectorSet function is used to update an existing element in a dynamic vector at a specified index. It ensures safe access by validating the index before modifying the vector’s content.

int vectorSet(vector *v, int index, void *item)
{
    int  status = UNDEFINE;
    if(v)
    {
        if ((index >= 0) && (index < v->vectorList.total))
        {
            v->vectorList.items[index] = item;
            status = SUCCESS;
        }
    }
    return status;
}

 

Step 6: Get the address of the data from the given index:

This function returns the address of the data at the specified index. If the index is valid, it provides a pointer to the stored element. Otherwise, it returns NULL (null pointer). The returned memory must be typecast to the appropriate data type before use.

void *vectorGet(vector *v, int index)
{
    void *readData = NULL;
    if(v)
    {
        if ((index >= 0) && (index < v->vectorList.total))
        {
            readData = v->vectorList.items[index];
        }
    }
    return readData;
}

 

Step 7: Removing an Element:

This function deletes the element at the specified index by setting it to NULL and shifting all subsequent elements one position to the left to maintain data continuity.

 

int vectorDelete(vector *v, int index)
{
    int  status = UNDEFINE;
    int i = 0;
    if(v)
    {
        if ((index < 0) || (index >= v->vectorList.total))
            return status;

        v->vectorList.items[index] = NULL;

        for (i = index; (i < v->vectorList.total - 1); ++i)
        {
            v->vectorList.items[i] = v->vectorList.items[i + 1];
            v->vectorList.items[i + 1] = NULL;
        }

        v->vectorList.total--;

        if ((v->vectorList.total > 0) && ((v->vectorList.total) == (v->vectorList.capacity / 4)))
        {
            vectorResize(v, v->vectorList.capacity / 2);
        }
        status = SUCCESS;
    }
    return status;
}

 

Step 8: Freeing Memory:

This function releases the allocated memory, ensuring efficient resource management and preventing memory leaks.

int vectorFree(vector *v)
{
    int  status = UNDEFINE;
    if(v)
    {
        free(v->vectorList.items);
        v->vectorList.items = NULL;
        status = SUCCESS;
    }
    return status;
}

 

Practice Code for Vector Implementation in C:

In this example, we create a vector of strings using the push_back function. After adding elements, we display the stored strings along with their indices. Additionally, we update a string at a specific index. It’s important to ensure that the data addresses remain valid to avoid dangling pointers. For best practices, refer to the article “How to Avoid Dangling Pointers.”

#include <stdio.h>
#include <stdlib.h>


#define VECTOR_INIT_CAPACITY 6
#define UNDEFINE  -1
#define SUCCESS 0


#define VECTOR_INIT(vec) vector vec;\
 vector_init(&vec)

//Store and track the stored data
typedef struct sVectorList
{
    void **items;
    int capacity;
    int total;
} sVectorList;


//structure contain the function pointer
typedef struct sVector vector;
struct sVector
{
    sVectorList vectorList;
//function pointers
    int (*pfVectorTotal)(vector *);
    int (*pfVectorResize)(vector *, int);
    int (*pfVectorAdd)(vector *, void *);
    int (*pfVectorSet)(vector *, int, void *);
    void *(*pfVectorGet)(vector *, int);
    int (*pfVectorDelete)(vector *, int);
    int (*pfVectorFree)(vector *);
};


int vectorTotal(vector *v)
{
    int totalCount = UNDEFINE;
    if(v)
    {
        totalCount = v->vectorList.total;
    }
    return totalCount;
}

int vectorResize(vector *v, int capacity)
{
    int  status = UNDEFINE;
    if(v)
    {
        void **items = realloc(v->vectorList.items, sizeof(void *) * capacity);
        if (items)
        {
            v->vectorList.items = items;
            v->vectorList.capacity = capacity;
            status = SUCCESS;
        }
    }
    return status;
}

int vectorPushBack(vector *v, void *item)
{
    int  status = UNDEFINE;
    if(v)
    {
        if (v->vectorList.capacity == v->vectorList.total)
        {
            status = vectorResize(v, v->vectorList.capacity * 2);
            if(status != UNDEFINE)
            {
                v->vectorList.items[v->vectorList.total++] = item;
            }
        }
        else
        {
            v->vectorList.items[v->vectorList.total++] = item;
            status = SUCCESS;
        }
    }
    return status;
}

int vectorSet(vector *v, int index, void *item)
{
    int  status = UNDEFINE;
    if(v)
    {
        if ((index >= 0) && (index < v->vectorList.total))
        {
            v->vectorList.items[index] = item;
            status = SUCCESS;
        }
    }
    return status;
}

void *vectorGet(vector *v, int index)
{
    void *readData = NULL;
    if(v)
    {
        if ((index >= 0) && (index < v->vectorList.total))
        {
            readData = v->vectorList.items[index];
        }
    }
    return readData;
}

int vectorDelete(vector *v, int index)
{
    int  status = UNDEFINE;
    int i = 0;
    if(v)
    {
        if ((index < 0) || (index >= v->vectorList.total))
            return status;

        v->vectorList.items[index] = NULL;

        for (i = index; (i < v->vectorList.total - 1); ++i)
        {
            v->vectorList.items[i] = v->vectorList.items[i + 1];
            v->vectorList.items[i + 1] = NULL;
        }

        v->vectorList.total--;

        if ((v->vectorList.total > 0) && ((v->vectorList.total) == (v->vectorList.capacity / 4)))
        {
            vectorResize(v, v->vectorList.capacity / 2);
        }
        status = SUCCESS;
    }
    return status;
}

int vectorFree(vector *v)
{
    int  status = UNDEFINE;
    if(v)
    {
        free(v->vectorList.items);
        v->vectorList.items = NULL;
        status = SUCCESS;
    }
    return status;
}


void vector_init(vector *v)
{
    //init function pointers
    v->pfVectorTotal = vectorTotal;
    v->pfVectorResize = vectorResize;
    v->pfVectorAdd = vectorPushBack;
    v->pfVectorSet = vectorSet;
    v->pfVectorGet = vectorGet;
    v->pfVectorFree = vectorFree;
    v->pfVectorDelete = vectorDelete;
    //initialize the capacity and allocate the memory
    v->vectorList.capacity = VECTOR_INIT_CAPACITY;
    v->vectorList.total = 0;
    v->vectorList.items = malloc(sizeof(void *) * v->vectorList.capacity);

}

int main(int argc, char *argv[])
{
    int i =0;

    //init vector
    VECTOR_INIT(v);
    //Add data in vector
    v.pfVectorAdd(&v,"aticleworld.com\n");
    v.pfVectorAdd(&v,"amlendra\n");
    v.pfVectorAdd(&v,"Pooja\n");

    //print the data and type cast it
    for (i = 0; i < v.pfVectorTotal(&v); i++)
    {
        printf("%s", (char*)v.pfVectorGet(&v, i));
    }


    //Set the data at index 0
    v.pfVectorSet(&v,0,"Apoorv\n");

    printf("\n\n\nVector list after changes\n\n\n");

    //print the data and type cast it
    for (i = 0; i < v.pfVectorTotal(&v); i++)
    {
        printf("%s", (char*)v.pfVectorGet(&v, i));
    }


    return 0;
}

Output: 

 

Recommended Articles for you:

• How to create dynamic array in C?
• How to access 2d array in C?
• Function pointer in c, a detailed guide
• How to use the structure of function pointer in c language?
• Function pointer in structure.
• Implement own memmove in C.
• memmove vs memcpy.
• Implement own memcpy in C.
• How to Use strncpy() and implement own strncpy().
• How to pass an array as a parameter?
• Implement own atoi in C.
• How to use C if-else condition?
• How to use for loop in C?
• You should know while loop use.
• Operators with Precedence and Associativity.
• Pointer Arithmetic in C.
• void pointer in C.
• A brief description of the pointer in C.
• Dangling, Void, Null and Wild Pointers
• When and how to use array in C?
• Memory Layout in C.
• File handling in C, In a few hours.