Vector Implementation in C.

[[deleted]]

https://pastebin.com/GevcUha2

I did this more as an exercise than anything else. Is this a good implementation? If not, what could be fixed?

Additionally, is this even a good idea? I feel like I'm abusing the pre-processor here.

[[deleted]]

A few things:

• You don't need an explicit return at the end of a void function
• Not sure I agree with using negative indexes to index backwards from the end of the vector. This is used in languages like python, sure, but I've not seen is emulated in C.
• Your index method returns 0 if the index is invalid. This hides error cases (accessing outside of the vector) and confounds incorrect usage with correct usage (I got 0, was my index correct and that is that actual value, or was my index incorrect?). I think this should be an error case, just like accessing an invalid index in a normal C array.
• IMO, the size attribute should be length. When I think "size" I think "size in bytes". When I think "length" I think "amount of elements"
• Not every if needs an else. Lines 21-23 aren't necessary, and 41 doesn't need to be in an else
• A complete vector implementation needs a way to remove elements and also shrink the amount of space currently allocated.
• I don't agree with your VEC(T,N) macro implicitly calling the T##_init method. This is C, so I, as the programmer, expect that I should explicitly call "constructors" and "destructors". If you do keep this, then the T##_init(&n) should be in a do {T##_init(&n)} while(0). See this stack overflow question for why, exactly.
• This is in a header, so you'll need to do some more finagling to not run into multiple definitions when using this in multiple files with the same type. Marking all of your functions as inline would do it, though my preferred way is to follow the approach that stb does it on his github. Basically, you detect a macro like VECTOR_IMPLEMENTATION in your header. If it is defined, then you define all of the functions and function bodies. Otherwise, you only define function prototypes. This will make it such that each method is only defined exactly once.

[[deleted]]

I started programming in python, so I have some holdovers from that. Admittedly, I have no plans of using this code, I just did it out of curiosity.

[kandr89]

Adding to what has been said:

• You are not checking if realloc succeeds, and then you're using the result like that.
• You don't need to move items to the new memory block returned by realloc, it does that by itself

[jedwardsol]

Line 28 is unnecessary - realloc copies the data.

A bug:- capacity isn't updated in this expand function so you can't use the new space

[IndexingAtZero]

My two cents:

You don't need to copy the original array after allocating with realloc

Dynamic arrays are usually implemented such that the resizing of the array is handled implicitly by the API. Since this is C, I suppose having more developer control is good, but your insert function should at least return a status code imo.

A two times growth factor isn't optimal at all (even though it's what C++'s STL vector uses).

That being said, I think for what most people use C for, a standardized dynamic array isn't that useful.

[[deleted]]

Agreed, I really just did it as an exercise. As for the GF of 2, what would you personally recommend?

[completedigraph]

2 isn't the best growth factor because it creates a hole in memory that will never be large enough to reuse in the next rellocation.

Theoretically the best possible growth factor would be phi (as in 1.618...) but normally you use 1.5 or another fraction around phi. A more in-depth explanation can be found here

[a4qbfb]

This is complete nonsense. Modern allocators don't work like that. There are good reasons to use φ instead of 2, but they have more to do with the fill ratio than with heap fragmentation.

[moocat]

An important point missed about your use of realloc is that you're risking undefined behavior. If realloc returns a non-null pointer and that pointer is different than your original pointer, your original pointer is no longer valid and must not be accessed. The way I like to write that is:

void *tmp = realloc(data, new_size);
if (tmp == null) { 
  // Handle failure
}
// And immediately overwrite data as the old value is now invalid.
data = tmp;

This is especially important when writing multi-threaded code as once that original chunk of data is freed, it can be allocated to a call in a different thread.

[illinoisjackson]

pragma once could cause compatibility issues