What does a "vector" that can dynamically grow need to keep track of?
- A current size.
- An allocated memory size.
- A (pointer to a) chunk of dynamically allocated memory, which can be reallocated when the vector needs to grow in size.
One that can store int values.
typedef struct int_vec {
size_t sz;
size_t allocated_sz;
int *data;
} int_vec_t;
When you want to allocate a vector you can use malloc to allocate the vector struct, but also the array that the data member will point to.
int_vec_t *make_int_vec(size_t starting_capacity) {
int_vec_t *vec = malloc(sizeof(*vec));
if (!vec) return NULL;
vec->data = malloc(sizeof(int) * starting_capacity);
if (!vec->data) {
free(vec);
return NULL;
}
vec->sz = 0;
vec->allocated_sz = starting_capacity;
return vec;
}
When you want a vector to grow it's best to do this by a factor other than +1. For simplicity, let's use x2. You'd use realloc to accomplish this, but in case realloc fails, we use a pointer other than vec->data to test it so we don't leave the original pointer dangling. Once we know it succeeded we can assign it to vec->data.
int_vec_t *grow_int_vec(int_vec_t *vec) {
if (!vec) return NULL;
int *new_data = realloc(vec->data, sizeof(int) * vec->allocated_sz * 2);
if (!new_data) return NULL;
vec->data = new_data;
vec->allocated_size *= 2;
return vec;
}
Remember on freeing such a structure you need to free the internal array as well. Two malloc calls were made to bring this struct into existence, so two free calls are needed to destroy it.
void free_int_vec(int_vec_t *vec) {
if (vec) free(vec->data);
free(vec);
}
If we wanted to write a push_onto_int_vec function, it might look like the following. A return value of NULL indicating that the element was not added, otherwise returning the vector.
int_vec_t *push_onto_int_vec(int_vec_t *vec, int val) {
if (!vec) return NULL;
if (vec->sz == vec->allocated_sz && !grow_int_vec(vec))
return NULL;
vec->data[vec->sz++] = val;
return vec;
}
