C vector

[lazy_cod3R]

im trying to write a vector in C and i am finding it very difficult.
I have written a linked list without to much trouble but the vector is just not working.

I dont understand how im supposed to allocate memory for a data types that will be stored in the vector, it could be a char*, int* anything and i dont know how im supposed to allocate the memory.

in c++ i would use templates
in java i would use a collection of objects

for the linked list in C i did


typedef struct {
LNode* next_ptr;
LNode* prev_ptr;
void* Data_ptr // this is the unknow data
}LNode;


but for the vector i dont know what kind of pointer to keep.
For example i tried


typedef struct {
void* myArrayOfData
}LVector;


and in my insert method i tried to create memory like so.

void List_insert(void* Data){
#define EACH_ELEMENT 512
void *data=malloc(EACH_ELEMENT*(prev_size+1));
}


Once i have done that i insert the new element given from the parameter into the last element of the data variable and it says illegal type void, so basiclly its saying i cant assign a void variable, what am i to declare this as if i have no idea what the user is going to type and what do i cast the new memory as ?

Thanx for any help

[debiandude]

If your creating an array of scalars you will need to define it as a pointer to a pointer (**) and malloc twice one for elements and again for each elements length or instead of a void * declare it a char *somearray[MAXLENGTH]

[Super Bakemono]

typedef Struct {
Vector *prev;
Vector *next;
void *data;
int sizeofdata;
} Vector;
int main(int argc, char **argv) {
Vector *vector;
vector = (Vector *)malloc(sizeof(Vector));
vector->data = (char *)malloc(sizeof(char));
vector->sizeofdata = sizeof(char);
return 0;
}

[Super Bakemono]

that's not really a vector, but that's how I would do the pointer to the data

[lazy_cod3R]

Ahh ok i understand , but what if the data i want to enter is not a char, what if it was also another struct, say a people struct ? would the data variable be able to store the people structs correctly ? would casting it out to a char cause an error if i wanted to store other objects in the data variable ?

thanx

[pinoy]

If you're trying to create a C version of the C++ vector, a C++ vector is just a growable array. Not a linked list. I should be able to take a pointer to it, increment it by 3 and get the third element, etc.

Without templates, I can only think of implementing this with some hacks and macros.

eg. If allocate an array of ints, I will prepend it with a header so I know how long the array is, how many elements used.


typedef struct {
size_t capacity;
size_t size;
/* etc... */
} vector_header;

int *int_vector_create(size_t size)
{
char *p = (char*)malloc((sizeof(int) * size) + sizeof(vector_header));
vector_header *hdr = (vector_header*)p;
p += sizeof(vector_header);
hdr->capacity = size;
hdr->size = 0;
return p;
}

void vector_free(void *p)
{
((char*)p) -= sizeof(vector_header);
free(p);
}

void int_vector_add(int *vector, int elem)
{
vector_header *hdr = ((char*)vector) - sizeof(vector_header);
if (hdr->size == hdr->capacity) {
/* reallocate */
}

vector[hdr->size++] = elem;
}


My implementation above basically returns an int array, but I've prepended some information into that array, that users won't find. You can then supply functions to manipulate the array, eg. to find out length of the array, etc. (these functions will also have to update the header).

I've also hard coded it to int types, this is where macros are useful. Anyway, vector is a simple type, without support for templates and operator overloading, I wouldn't bother implementing such beasts.

[pinoy]

Also, here's an example of how I would use the above code. (Note, I haven't tested/compiled any of these codes)


int main(void)
{
/* create an array of 3 ints */
int *x = vector_create(3);
int i;

/* the vector should automatically grow */
for (i = 0; i < 10; i++)
vector_add(x, i);

printf("Element 5 is: %d\n", x[5]);
vector_free(x);
return 0;
}

[lazy_cod3R]

If you're trying to create a C version of the C++ vector, a C++ vector is just a growable array. Not a linked list. I should be able to take a pointer to it, increment it by 3 and get the third element, etc.


Yes i was trying to make a growable array, i basiclly didnt know what type to make the array though, what i stated above was that i had done a linked list but now i wanted to try my hand at a vector.
Im very new at C (learnt things backwards, from 00 programming with java -> C++ -> perl and now C)and still have lots to learn in C so i am not quite sure what a macro is and even how to use them, so i might have to look at how to use them before trying anything further.

Thanx for your help pinoy, your previous post on atemptting to put functions in C structs was very helpful.

[pinoy]

Thanx for your help pinoy, your previous post on atemptting to put functions in C structs was very helpful.


No problem, that's what this forum is for. Anyway, macros are those #define things. They're processed by the preprocessor, before the compiler actually gets to it. The reason I thought macros would be useful in this case is because you need to know what the types are in the array. You could pass the type to a macro which would then generate the appropriate "vector" code.

This is easy in C++ because of templates. Templates allows you to parameterize types, in fact they're templates number one job. This is not exactly OO though, it's actually "generic" programming.

BTW, having functions inside struct is also not OO. You are merely converting your coding convention to: func(obj), to obj.func(obj). OO's power is in polymorphism and this is done through virtual functions (something not easily done in C).

[Stuka]

Y'know, while a vector is, by definition, an expandable array, a doubly-linked list is not necessarily an awful implementation (at least for small vectors). Remember that the underlying data structure does not necessarily have to look like what the user of the structure thinks it does. To really do up a vector right, first develop your interface (your header file) so that it gives an expected vector interface. Then decide on a data structure (linked list, fixed array that gets allocated/copied/reallocated as necessary, etc.), and write the implementation based on that data structure. If the performance is unacceptable, find a better data structure! ;)
<edit>Oh, and if you're writing generic data structures in C, use void* for your data pointers - the user SHOULD know what he/she is putting in, and can cast it appropriately coming out.</edit>

[ 20 September 2001: Message edited by: Stuka ]

[pinoy]

Remember that the underlying data structure does not necessarily have to look like what the user of the structure thinks it does.

No. A vector should have the same semantics as an array. You may have a pointer to a different type, but the underlying data should be a block of contiguous memory. ie. A pointer to a vector's data should look like an array, and you should be able to manipulate the pointer as if it was a pointer to an array. A linked-list will not do, because you can't do random access pointer on a list. You have to walk the list to get the element.


Oh, and if you're writing generic data structures in C, use void* for your data pointers - the user SHOULD know what he/she is putting in, and can cast it appropriately coming out.

I thought about using a void*, but remember you have to call a function to add an element. e.g push_back, or vector_add, so it can reallocate the data if needed. The problem is how much data does the user copy into the array. It depends if your passing a pointer or the actual data. I guess a void* will work, if you also tell the vector that you're adding a pointer, or an actual data. I'm sure you can make it work with void*, this was exactly my initial solution, but later thought that this was messy, considering how easy it is to do with templates.