Representing vectors using structures

Question

I was recently asked to represent a structure using a struct data type. As per my knowledge, a vector is represented as (10, 20, 30, 40 etc. ) It appears that it would be easier to access a vector by an indexed data structure, like an array. But I do not know how many members I would be needing in the struct data type. Then how will I define the structure ?

Answer 1

A vector is basically a dynamic array, meaning that the underlying type is a pointer to an array, each time you add something, the array increases by one. In a very basically this would lead to a costly copy each time this was done; this is way they mostly try to either predict the next size ( by doubling the amount of available slots) or allowing one to resize to a best-guess, which, if missed, will still result in doubling. Anyway, an insert (thus not at the end of the array) will still require a costly copy. This means that a vector will be interesting for random access reads of data, while not so for writes.

When you look at the O-complexity, you'll see that this now makes sense.

• Random access - constant O(1)
• Insertion or removal of elements at the end - amortized constant O(1)
• Insertion or removal of elements linear in distance to the end of the vector O(n)

Knowing about the several data-containers is crucial to understand which one to pick under which circumstances. More often then not, I see programmers always using a vector (even the ones that are doing the job long enough to understand when to use which container).

I'm sure this explanation will give you enough to implement the real thing ;-)

sources:

• http://en.cppreference.com/w/cpp/container/vector

Answer 2

In C99, you can define an FAM struct.

struct vector {
  size_t len;
  int vals[];
};

Then you can dynamically allocate instances of the struct, depending on the length you need.

struct vector* v = malloc(sizeof(struct vector) + (n * sizeof(v->vals[0]));
v->len = n;

for (int i = 0; i < v->len; i++)
  v->vals[i] = i;

A higher dimensional structure (e.g. matrix) is a bit trickier, but I'm not sure if you need that.

Answer 3

If I wanted to represent an int vector in C, I would use:

• a malloc'd array
• a variable tracking allocated size
• a variable tracking used length

It gives:

struct int_vector {
    int *arr;
    unsigned int len;
    unsigned int size;
};

Access to arr is legal for 0<=i<len.

I would add some utilities:

int resize(struct int_vector *vec, unsigned int new_len) {
    if (new_len > vec->size) {
        void *p;
        unsigned int size = vec->size;
        while(new_len > size) size *= 2;
        *p = realloc(vec->arr, sizeof(int) * size);
        if (p == NULL) return 0; /* cannot realloc */
        vec->arr = p;
        vec->size = size;
    }
    vec->len = new_len;
}

You can then easily implement push and pop:

unsigned int push(int_vector *vec, int val) {
    if (resize(vec, vec->len + 1) == 0) return 0;
    vec->arr[vec->len -1] = ival;
    return vec->len;
}
int pop(int_vector *vec) {
    vec->len -= 1;
    return vec->arr[vec->len];
}

You could implement a truncate function to reduce the allocated size, but this is a simplistic but working example.

Unfortunately, as C has neither generics not templates, you would have to define a vector class for every and each type that you want to process...