Will03uk
Will03uk

Reputation: 3444

What's the best c implementation of the C++ vector?

I've been looking into using C over C++ as I find it cleaner and the main thing I find it to lack is a vector like array.

What is the best implementation of this?

I want to just be able to call something like vector_create, vector_at, vector_add, etc.

Upvotes: 9

Views: 16087

Answers (6)

Evan Teran
Evan Teran

Reputation: 90503

EDIT

This answer is from a million years ago, but at some point, I actually implemented a macro-based, efficient, type-safe vector work-alike in C that covers all the typical features and needs. You can find it here:

https://github.com/eteran/c-vector

Original answer below.


What about a vector are you looking to replicate? I mean in the end, it all boils down to something like this:

int *create_vector(size_t n) {
    return malloc(n * sizeof(int));
}

void delete_vector(int *v) {
    free(v);
}

int *resize_vector(int *v, size_t n) {
    return realloc(v, n * sizeof(int));
    /* returns NULL on failure here */
}

You could wrap this all up in a struct, so it "knows its size" too, but you'd have to do it for every type (macros here?), but that seems a little uneccessary... Perhaps something like this:

typedef struct {
    size_t size;
    int *data;
} int_vector;

int_vector *create_vector(size_t n) {
    int_vector *p = malloc(sizeof(int_vector));
    if(p) {
        p->data = malloc(n * sizeof(int));
        p->size = n;
    }
    return p;
}

void delete_vector(int_vector *v) {
    if(v) {
        free(v->data);
        free(v);
    }
}

size_t resize_vector(int_vector *v, size_t n) {
    if(v) {
        int *p = realloc(v->data, n * sizeof(int));
        if(p) {
            v->data = p;
            v->size = n;
        }
        return v->size;
    }
    return 0;
}

int get_vector(int_vector *v, size_t n) {
    if(v && n < v->size) {
        return v->data[n];
    }
    /* return some error value, i'm doing -1 here, 
     * std::vector would throw an exception if using at() 
     * or have UB if using [] */
    return -1;
}

void set_vector(int_vector *v, size_t n, int x) {
    if(v) {
        if(n >= v->size) {
            resize_vector(v, n);
        }
        v->data[n] = x;
    }
}

After which, you could do:

int_vector *v = create_vector(10);
set_vector(v, 0, 123);

I dunno, it just doesn't seem worth the effort.

Upvotes: 11

potrzebie
potrzebie

Reputation: 1798

If you can multiply, there's really no need for a vector_create() function when you have malloc() or even calloc(). You just have to keep track of two values, the pointer and the allocated size, and send two values instead of one to whatever function you pass the "vector" to (if the function actually needs both the pointer and the size, that is). malloc() guarantees that the memory chunk is addressable as any type, so assign it's void * return value to e.g. a struct car * and index it with []. Most processors access array[index] almost as fast as variable, while a vector_at() function can be many times slower. If you store the pointer and size together in a struct, only do it in non time-critical code, or you'll have to index with vector.ptr[index]. Delete the space with free().

Focus on writing a good wrapper around realloc() instead, that only reallocates on every power of e.g. 2 or 1.5. See user786653's Wikipedia link.

Of course, calloc(), malloc() and realloc() can fail if you run out memory, and that's another possible reason for wanting a vector type. C++ has exceptions that automatically terminate the program if you don't catch it, C doesn't. But that's another discussion.

Upvotes: 0

kichik
kichik

Reputation: 34744

Apache Portable Runtime has a decent set of array functions and is all C.

See the tutorial for a quick intro.

Upvotes: 0

user786653
user786653

Reputation: 30480

Rather than going off on a tangent in the comments to @EvanTeran's answer I figured I'd submit a longer reply here.

As various comments allude to there's really not much point in trying to replicate the exact behavior of std::vector since C lacks templates and RAII.

What can however be useful is a dynamic array implementation that just works with bytes. This can obviously be used directly for char* strings, but can also easily be adapted for usage with any other types as long as you're careful to multiply the size parameter by sizeof(the_type).

Upvotes: 0

Ben Jackson
Ben Jackson

Reputation: 93880

The most complete effort I know of to create a comprehensive set of utility types in C is GLib. For your specific needs it provides g_array_new, g_array_append_val and so on. See GLib Array Documentation.

Upvotes: 1

K-ballo
K-ballo

Reputation: 81379

Lack of template functionality in C makes it impossible to support a vector like structure. The best you can do is to define a 'generic' structure with some help of the preprocessor, and then 'instantiate' for each of the types you want to support.

Upvotes: -1

Related Questions