Implement Vector in C

In my previous article, I have explained how we can create a dynamic array in C.  But my reader says to write an article to create a vector in C. Basically vector is a dynamic array that has the ability to resize itself automatically when an element add or removed from the vector.

A vector element store in a continuous manner so we can access the element using the index. It is great and also likes the linked list we don’t need to allocate the memory for each node. We allocate the extra memory in the beginning and adjust it as per the requirement.

So let’s come on the topic and create a simple vector. Because C is not supported to the template and vector so here I am creating a vector using the structure and pointer. This vector will store the address of the element using the void * (Generic pointer, you can see this article). The advantage of the void pointer is that we can store the address of any data type.

Code implementation of the vector in C

First, we need to create a structure that stores the data and also track the stored data. I am also creating here another structure to store the function pointer which points to the vector function (because C does not support the function in a structure like C++).

//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 *);
};

 

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)

 

 

Vector initialization:

In this function, I am initializing the capacity of the vector 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);

}

 

Resize the vector:

This function allocates the memory with a new size using realloc library function and updates the tracking parameter with the new value. You can also see the article, How to allocate dynamic memory in C.

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;
}

 

 

Push Back function:

This function inserts the data at the end of the vector. If sufficient memory is not available then it will resize the memory.

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;
}

 

Set data at a given index:

This function sets the data at the given index if the index is valid. If you will pass the invalid index then it will do nothing.

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;
}

 

 

Get the address of the data from the given index:

If the index is valid then this function will return the address of the data of the given index. If the index is not valid then it will return NULL (null pointer). You need to typecast the memory as per the data types.

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;
}

 

Delete the data of the given index:

This function assigns the NULL to the given index and shifts all elements in vector by 1.

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;
}

 

Free the allocated memory:

This function deallocates the allocated memory.

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

 

 

Example Code of a vector in C:

In this example, I am creating a vector of string using the pushback function.  After creation the vector I am displaying the stored string with there index. I have also set the string using the index. You should remember that the address of the data should be valid and you have to care about the dangling pointer. You can also see this article “How to avoid dangling pointer“.

#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.