euisblue
.about.project.blog.cp.dsa
.about.project.blog.cp.dsa
[C] Vector (mutable array) implementation
Use arrays to implement a mutable array with automatic resizing  

    Here are lists of functions to implement for the vector:

    Private function

    • resize(new_capacity)
      • double the capacity when vector is full
      • halve the capacity if size is 1/4 of capacity

    Public function

    • size() - returns number of items in vector
    • capacity() - returns number of items it can hold
    • is_empty() - returns true if empty, else false
    • at(index) - returns item at given index
    • push_back(data) - adds data at the end of the vector
    • pop_back() - removes the data from the end and returns it
    • prepend(data) - inserts data at index 0
    • insert(index, data) - inserts data at index, shifts that index's value and trailing elements to the right
    • delete(index) - deletes data at index and shift all trailing elements left
    • remove(data) - find and remove all data from the vector
    • find(data) - looks for value and returns first index with that value, -1 if not found

    Things to keep in mind:

    • Time complexity
      • constant time to add and remove data at the end, access, or update.
      • linear time to insert or remove elsewhere because of shifting.
    • Space complexity
      • linear -> (array capacity) * (size of data)

    Implementation

    TL;DR -- source code

    Vector structure

    I first defined a structure for the vector:

    1typedef struct {
2  int *arr;
3  int capacity;
4  int size;
5} Vector;

    arr is the array and it's declared as a pointer since it's a mutable array. So it needs to be dynamic not static.

    I implemented init() function to initialize the vector and destroy() function to destory the instance at the end.

    1#define INF 0x7FFFFFFF
2#define DEFAULT_SIZE 16
3
4void init(Vector *vec) {
5  vec->capacity = DEFAULT_SIZE;
6  vec->size = 0;
7  vec->arr = (int *)(malloc(DEFAULT_SIZE * sizeof(int)));
8
9  // initialize the element as infinity 
10  for(int i=0; i<DEFAULT_SIZE; ++i) {
11    (vec->arr)[i] = INF;
12  }
13}
14
15void destroy(Vector *vec) {
16  free(vec->arr);
17  vec->arr = NULL;
18  vec->size = 0;
19  vec->capacity = 0;
20}
21
22int main() {
23    Vector vec;
24    init(&vec);
25    
26    ...
27
28    destory(&vec);
29
30    return 0;
31}

    Resize the vector

    Before we talk about adding/removing data, lets take a look at how resizing is done.

    We have 2 cases for resizing:

    1. if the vector is full and need to double the capacity.
    2. if number of data in vector is 1/4 of capacity and need to halve the capacity.

    We can check conditions and determine whether to double or halve the capacity in resize, but I didn't wanted to do that.

    1static void resize(Vector *vec, int capacity) {
2  vec->capacity = capacity;
3  int *temp = (int *)(malloc(vec->capacity * sizeof(int)));
4
5  // copy over data
6  for(int i=0; i<vec->size; ++i) {
7    temp[i] = (vec->arr)[i];
8  }
9
10  free(vec->arr);
11  vec->arr = temp;
12}

    When adding or removing data, we will check the size and pass in the appropriate capacity in resize. Then this function will create a new array with the new capacity, copy over existing data, and re-assign the instance's array.

    Add data at the end

    If we have 5 elements in the vector, vec->size will be 5, but the index 5 means the 6th element. So we can use vec->size to add a data at the end in constant time. But we need to make sure that we have enough space. When vector is full, we double the capacity by calling the function resize with doubled capacity.

    1void push_back(Vector *vec, int size) {
2  // double the size if vector is full
3  if(vec->size == vec->capacity) {
4    resize(vec, vec->capacity << 1);
5  }
6
7  (vec->arr)[vec->size] = size;
8  ++(vec->size);
9}

    Insert data in the beginning

    We need to shift all elements once to the right to empty the first element. Resizing is already covered, so no need worry about going off the boundary when shifting data.

    1void prepend(Vector *vec, int data) {
2  // double the size if vector is full
3  if(vec->size == vec->capacity) {
4    resize(vec, vec->capacity << 1);
5  }
6
7  ++(vec->size);
8  for(int i=(vec->size)-1; i>0; --i) {
9    (vec->arr)[i] = (vec->arr)[i-1];
10  }
11
12  (vec->arr)[0] = data;
13}

    Insert data at any index

    If inserting in the beginning or at the end, I utilized functions that I implemented earlier: prepend and push_back. For the other case, I shifted all elements from given idx to the end once to the right.

    1void insert(Vector *vec, int idx, int data) {
2  // double the size if vector is full
3  if(vec->size == vec->capacity) {
4    resize(vec, vec->capacity << 1);
5  }
6
7  if(idx == 0) {
8    prepend(vec, data);
9  } else if (idx >= vec->size) {
10    push_back(vec, data);
11  } else {
12    ++(vec->size);
13    for(int i=vec->size-1; i>idx; --i) {
14      (vec->arr)[i] = (vec->arr)[i-1];
15    }
16
17    (vec->arr)[idx] = data;
18  }
19}

    Remove data at the end

    Removing is straightforward. Simply set the last element to null or INF in this case. Once you removed an element, check if the size is smaller than that of quarter of the capacity. If so, halve the total capacity.

    1int pop_back(Vector *vec) {
2  if(is_empty(vec)) {
3    printf(".... vector is empty\n");
4    return -1;
5  }
6
7  // if size is 1/4 of capacity, halve the capacity
8  int quart = vec->capacity / 4;
9  if(vec->capacity > DEFAULT_SIZE && vec->size <= quart) {
10    resize(vec, vec->capacity >> 1);
11  }
12
13  --(vec->size);
14  int data = (vec->arr)[vec->size];
15  (vec->arr)[vec->size] = INF;
16
17  return data;
18}

    Remove data at any index

    When given index is greater than the total number of elements, instead of throwing an error, I decided to remove the last element by calling pop_back.

    When the index is somewhere between, I shift all the elements once to the left starting from the given idx.

    1int delete(Vector *vec, int idx) {
2  if(idx >= vec->size) {
3    return pop_back(vec);
4  }
5
6  int data = (vec->arr)[idx];
7
8  for(int i=idx; i<vec->size; ++i) {
9    (vec->arr)[i] = (vec->arr)[i+1];
10  }
11
12  --(vec->size);
13  (vec->arr)[vec->size] = INF;
14  
15  return data;
16}

    Remove all data that matches the given value

    I used a temporary array to store all elements that isn't the value to delete.

    As I iterate the array, I will have a separate index(p) which tracks down the element that we're going to keep. Eventually the p will become the total size after the removal.

    1void _remove(Vector *vec, int value) {
2  if(is_empty(vec)) return;
3
4  int p = 0;
5  int *temp = (int *)(malloc(vec->capacity * sizeof(int)));
6  for(int i=0; i<vec->size; ++i) {
7    if((vec->arr)[i] != data) {
8      temp[p] = (vec->arr)[i]; 
9      ++p;
10    }
11  }
12
13  vec->size = p;
14  free(vec->arr);
15  vec->arr = temp;
16
17  // if size is 1/4 of capacity, halve the capacity
18  int quart = vec->capacity / 4;
19  if(vec->capacity > DEFAULT_SIZE && vec->size <= quart) {
20    resize(vec, vec->capacity >> 1);
21  }
22}

    Find data

    Iterate the array and check if the data is what we're looking for. If found, return that index else return -1.

    1int find(Vector *vec, int data) {
2  int idx = -1;
3
4  for(int i=0; i<vec->size; ++i) {
5    if((vec->arr)[i] == data) {
6      idx = i;
7      break;
8    }
9  }
10
11  return idx;
12}