Thread: Pure C Vector

Hello everyone, I have a question regarding best practices/methodology.

I am implementing a vector in C. I am doing this for the fun of programming, for the fun of learning, and for the use of the data structure in later projects.

Now, I have read over many implementation examples and most of them take the size of an individual element as an argument to the Vector_create() function, and use this for later memmove()/memcpy() calls and what not and more or less keep (for instance) the vector's elements in contiguous memory. In other words, the underlying array is essentially a single void*.
In the implementation I wrote before doing a lot of looking at how other people have done it, I allow(force) the client code to allocate an "object" and pass that as a pointer to the Vector_append()function. So my underlying array is a void**. So I guess the real question I am asking is if this is wrong. Wrong as in best practices wrong.

I see that the "normal" way of doing this doesn't use an array of pointers and instead just copies the memory of a struct (for example) into the underlying void* array and thereby keeping the actual data of the elements contiguous, as mentioned earlier. My way avoids a crap load of memmove()/memcpy() because I just copy pointer values, however, I am forcing the client to malloc() everything that is sent to the vector, and thereby do a bunch of screwing around on the heap.

Along those lines, I do call free() on the underlying data item when the item is removed, so the vector library does a free() that the vector library never did the original malloc() on. Is this bad practice too? The only trouble I seem to get into is if there was a member variable (for lack of a better term) that points to dynamic memory within the struct. It then becomes the client responsibility to free() that data, but again, the struct itself is freed from within the vector library call Vector_remove().

Lets say you have this as a struct you want to store in your vector.

Code:

struct foo {
    size_t  stringLen;
    char   *stringPtr;
};

Where stringPtr points to a block of allocated memory, and stringLen is the length of that memory.

If you take the simple case of just block copying the memory, you won't be taking into account the special nature of the pointer. You've have two copies of the foo object (one in your vector, and one outside), but only one block of allocated memory. This will create all sorts of difficulties, because the external copy has to be maintained as a read-only copy (you can't realloc stringPtr for example). Nor can you properly destroy the external copy without trashing the copy in your vector.

So perhaps you have
Vector_create( size_t size, void *(*copyFn)(void*,void*,size_t) )
where size is the size of the structure you want to store, and copyFn (which could be memcpy in the simple case) is a function that knows how to make a decent copy of some deeply nested structure.

You can extend this idea to your complicated "store pointers only" idea by also supplying your Vector_create function with a 'free' function that knows how to properly delete a deeply nested structure (which may just be free() itself in the simple case).

Are you intending to give users the raw base pointer and let them do whatever they want using [subscript] notation on that pointer?
Or will you provide get/set methods via some kind of opaque pointer to preserve stored value semantics.

You definitely need to think about what happens when you store nested structures, because you'll either have lots of memory leaks or lots of references to non-existent memory if you get it wrong.

Originally Posted by MutantJohn

Okay, I don't actually know what you want. You kind of explain it but the high view count and low reply count kind of indicate no one wants to touch this.So, a "vector" is the mathematical or physics sense is (x), (x, y) or (x, y, z). These are just simple coordinate vectors that would be used to represent points in 1D, 2D and 3D space.So when you say a pure C vector, I'm not sure what you mean. C doesn't have vectors, it has 'vectors' or something that would behave like a vector but in all reality isn't.And when you say the word vector, you're implying magnitude and direction, cross and dot products. What you seem to be doing is some form of networking programming and you want the best practices for that, i.e. should you force your clients to malloc? You don't vector help, you want networking or w/e it is help.

I am not referring to a vector in the physics sense (either 2D or 3D), and certainly not network programming; I am referring to the classic data structure called a vector, somewhat synonymous with "dynamic array."