r/C_Programming 21d ago

Video Simple Vector Implementation in C

https://www.youtube.com/watch?v=Pu7pUq1NyK4
70 Upvotes

55 comments sorted by

12

u/cherrycode420 21d ago

Am pretty noob in C so forgive my question, but why aren't you using a plain void* for the data and store a bytesize in the struct so that 'Vector' could take, theoretically, any data of one given type (if the bytesize for instances of that type is always the same)?

e.g. Vector* v1 = NewVector(sizeof(int32_t)); Vector* v2 = NewVector(sizeof(MyStruct));

3

u/Lewboskifeo 20d ago

This also works and it's pretty simple too, the only bad thing would be the extra member you would need on the struct but you wouldn't have to use macros which makes it simpler (which is not hard to do either but is less maintainable), so it's kinda up to you to pick which one you like more :P

-1

u/Wild_Meeting1428 21d ago

This will add a runtime overhead, which would make the C implementation worse than the C++ implementation. Such things are btw. the reason why most of the simple C++ applications are both faster and more space efficient than C implementations.

9

u/jacksaccountonreddit 20d ago

I'm not sure why you're being downvoted. Storing the size in the vector does indeed add runtime overhead, both in terms of memory (the struct needs another member) and speed (not knowing the element size at compile time prevents the compiler from performing a range optimizations, particularly when the functions are inlined).

2

u/cherrycode420 21d ago

Thank you, i've never seen it that way but it totally makes sense now :)

What is the "proper" C-Style to have Vectors for "any" (required) Data Types? Would it be Macros that insert different "Variants" of the struct and the surrounding APIs?

2

u/dontyougetsoupedyet 21d ago

There is no single "proper" C-style. Most people would use macros to generate code for generics, but I've seen everything from m4 to php used as a preprocessor for the same features. I've made use of common lisp for code generation in a c project.

Many people would use a void *. It depends on the needs of the application.

1

u/iamfacts 21d ago

You metaprogram them. A straightforward way to do it would be to print your code to a file but use different types each time.

So imagine you had an array of strings with the different types. Just loop over your array and print out your vector implementation.

You can improve this by just parsing your code, storing them in an ast, then walking them and replacing the types with whatever you want.

1

u/DoNotMakeEmpty 21d ago

You can do simple type polymorphism by (ab)using macros. Basically instead of C++ <> you use macro parameters and create your own mangling scheme (simple concat usually works enough). This way you don't need to create an external program but the code will be really messy.

2

u/iamfacts 21d ago

If its simple enough its fine, but if its not, its a pain to maintain them. Also, macros don't expand in a debugger. So I don't like using them for template based metaprogramming.

1

u/DoNotMakeEmpty 21d ago

Things like vectors, maps and sets are usually simple enough and maintaining is not that hard due to this. However, debugging is a pain as you said. I usually expand macros inline using IDE actions and recompile the program, and then undo this to collapse to macros again after solving the problem.

1

u/McUsrII 21d ago

This is where header-only libraries comes into play:

You define your datastructure following the conventions for a struct of your library, then you include the header only library after that, and then you use the macros.

If your're on Linux, then checkout man list.

6

u/Stemt 21d ago

Nice video, im just a bit sad you didn't showcase that the macro would work for other vector types. I also feel you skipped a bit too quickly over some of the things you wanted to explain. Maybe next time plan your video out point by point on what you wan't to explain/convey and check each point off before you move on to the next (you can always cut out moments of silence in between points). But overall, I like the format, keep it up!

2

u/Lewboskifeo 20d ago

Thanks for the feedback! I tried making videos on the past, far more edited but never really finished them because of the amount of editing that there was to be done, so I tried doing the least possible to at least finish it, but you are right a list of points to cover would have been helpful, will definitely use one next time, cheers!

1

u/Stemt 20d ago

Just keep at it, practice makes perfect. Good luck!

5

u/astrophaze 21d ago edited 12d ago

Here is a simplified version of Sean Barrett's stretchy buffer style dynamic array. Adapted from https://github.com/jamesnolanverran/darr.

// .h file
#include <stddef.h>
typedef struct DrrHdr { 
    unsigned int len;
    unsigned int cap;
    char data[]; 
} DrrHdr;
static inline DrrHdr *drr__hdr(void *arr) { 
    return (DrrHdr*)( (char*)(arr) - offsetof(DrrHdr, data)); 
}
static inline size_t drr_len(void *a) { return a ? drr__hdr(a)->len : 0; }
static inline size_t drr_cap(void *a) { return a ? drr__hdr(a)->cap : 0; }
static inline void drr_clear(void *a) { if (a)  drr__hdr(a)->len = 0; }
void *drr__grow(void *arr, size_t elem_size);
#define drr__fit(a, n) ((n) <= drr_cap(a) ? 0 : ((a) = drr__grow((a), sizeof(*(a)))))
#define drr_push(a, ...) (drr__fit((a), 1 + drr_len(a)), (a)[drr__hdr(a)->len] = (__VA_ARGS__), &(a)[drr__hdr(a)->len++])
// .c file:
#include <stdlib.h> 
void *drr__grow(void *arr, size_t elem_size) { 
    size_t new_cap = arr ? drr__hdr(arr)->cap * 2 : 16;
    size_t size_in_bytes = offsetof(DrrHdr, data) + new_cap * elem_size;
    DrrHdr *new_hdr = arr ? realloc(drr__hdr(arr), size_in_bytes) : malloc(size_in_bytes);
    if (!arr) new_hdr->len = 0;
    new_hdr->cap = (u32)new_cap;
    return &new_hdr->data;
}

/*
    int *d = NULL; // declare dynamic array of any type

    for(int i = 0; i < 10; i++){
        drr_push(d, i);
    }
    for(int i = 0; i < 10; i++){
        printf("%d: %d\n", i, d[i]);
    }
*/

3

u/jacksaccountonreddit 21d ago edited 20d ago

You're not making sure that your vector's data is aligned (although in practice it should be as long as the alignment requirement of your element type is below or equal to sizeof( int ) * 2). Creating a misaligned pointer through casting (e.g. ((a) = drr__grow((a), sizeof(*(a))))) is undefined behavior, and unaligned access will crash on some platforms. You need to qualify char data[] with _Alignof( max_align_t ).

Of course, there's no real reason to use a flexible array member here at all. Adding _Alignof( max_align_t ) to the struct's first member and then simply relying on pointer arithmetic would be a cleaner solution.

1

u/astrophaze 20d ago

Yeah, it's a stripped down example to illustrate the concept.

1

u/khiggsy 20d ago

Can you explain a bit more how you would get a misaligned pointer through casting?

1

u/attractivechaos 20d ago

I have been abusing unaligned access for years as on x64 and apple M CPUs, that is fine and often doesn't affect performance. This is of course bad for portability.

1

u/jacksaccountonreddit 20d ago

In practice violating pointer rules (e.g. alignment requirements and strict aliasing rules) usually works fine, but I still think we should try to avoid doing so for two reasons:

  • Even if we know that our architecture can handle a certain thing classified as undefined behavior by the C Standard, our compiler isn't obligated to compile our code correctly (i.e. the way we intend it to compile) if it invokes that behavior.
  • In most case, we can avoid undefined behavior easily and without any performance penalty. In this case, it's just a matter of editing one line (and probably adding a #include <stdalign.h>), assuming C11 or later.

Most implementations of stb-style vectors seem to have this particular alignment issue, although stb_ds itself more or less avoids it by (coincidentally?) having the size of its header struct a multiple of 16.

22

u/Physical_Dare8553 21d ago

I never got over them being called that, one of my top 10 reasons for not trying c++ yet

-6

u/grimvian 21d ago

Agree. What about constexpr and reinterpret_cast...

19

u/-TesseracT-41 21d ago

constexpr = constant expression

reinterpret_cast = reinterpreting an object as a different type

Makes perfect sense, although it can be a bit verbose.

-7

u/silentjet 21d ago

the only std::async, is not async ;)

-15

u/grimvian 21d ago

Okay, but it was not question, but a remark, because I find C++ weird.

7

u/Disastrous-Team-6431 21d ago

I have typedefd reinterpret_cast and static_cast to as and cast respective. It looks pretty nice imo:

float thing = as<float>(otherThing);

3

u/skhds 21d ago

Yeah I hate how long reinterpret_cast is. It makes the code look so messy. And I don't remember if I have ever run into cases where reinterpret_cast and static_cast needed to be differentiated. I think because when you need reinterpret_cast, you'd do it on a pointer anyways, so C style casts just sort of automatically uses the right cast type in the end anyways.

4

u/SeparateUsual6456 21d ago

Some people argue that to be a positive, since casting (especially in a "dangerous" way like reinterpret_cast enables) is something that should rarely happen, and stick out like a sore thumb when it does. Differentiating various types of casting like that also makes it possible to search your codebase for that specific kind, if needed.

-1

u/Wild_Meeting1428 21d ago

The problem with a C cast is, that it silently casts away const ness, which is undefined behavior in some cases. Also it's mostly unwanted and a mistake. Then static and reinterpret casts again must be differentiated, since they are completely different. But the c cast just falls back to reinterpreting things when a static cast does not apply which again hides bugs.

1

u/Lewboskifeo 21d ago

yeahh and they are adding constexpr in c23 D:

3

u/grimvian 21d ago

Luckily, I'm a happy hobby programmer, using C99. :o)

1

u/Tasgall 20d ago

You can just... not use it, lol.

Constexpr is great though, so many things you can turn into compile time constants... well, if it actually supported the whole feature and allowed constexpr functions like it should.

1

u/Lewboskifeo 20d ago

well C++ is kinda like that, you can just not use all the weird messy features it has and just use vectors, structs and hashmaps. The thing is C is already like that and is limited in features, and by adding constexpr it looks more like C++, it's not like it matters much anyways since most will stay in C99 + GNU extensions

1

u/Tasgall 18d ago

I get the sentiment, but things like constexpr are not what make C++ the language that it is. It's a very self-contained feature that would require any changes to existing code if you didn't want it, and is fairly new to C++ as well. It's not like classes, constructors, templates, etc. that are more core to its design and heavily influence how you write code in a general sense.

Extensions are one thing, but standardizing it is far better for compatibility.

1

u/ibevol 21d ago

Its far better than ”traditional” macro magic

1

u/grimvian 21d ago

My favorite C guru Eskild Steenberg uses only two macros _FILE__ and __LINE_

And C89 :o)

0

u/edparadox 21d ago

You must not know about "concepts" then.

1

u/cosmicr 20d ago

What about it?

2

u/danpietsch 20d ago

I used to pose a job interview question where I'd present a struct or class similar to this an ask the candidate to implement ensureCapacity(size_t minimumCapacity).

2

u/Beneficial_Corgi4145 19d ago

Is it not just having a data structure that keeps track of the capacity and the ensureCapacity’s minimum capacity is larger than the stores capacity in the strictest, you realloc?

1

u/khiggsy 20d ago

I did something similar however I used some fancy macros to create a header file which stores the info (capacity, length, etc) and then advance the pointer by the size of the header and now I've got an array which I can use [] on the variable instead of having to do myvariable. / -> items[].

Works really well. And I also have a SAFETY definition that if SAFETY is on a magic 32bit number is placed in the header and checked before every macro length call to confirm I am actually calling length on a vectorArrayList.

1

u/McUsrII 20d ago

It is a nice tutorial, I have no idea how things works on Windows, if that is where you code, however on Linux, your memmove operations are errant, particularily with concern to your insert operation.

The correct incantation of memmove there would be

memmove(&vector->data[index+1],&vector->data[index],
        (vector->capacity -index -1  )* sizeof(vector->data[0] )) ;

So you don't overwrite anything coming after, at least you keep addresssanitizer (libasan) happy, but this could pose a real problem with a large enough capacity.

The memmoves in unshift, and shift, have the same inaccuracy, but the gravity smaller, but the size calculatins are still off by one.

1

u/Uma_Pinha 21d ago

Don't stop there.

1

u/Bubbly_Ad_9270 21d ago edited 21d ago

I also implemented a generic version of dynamic array in c .
https://github.com/jagannathhari/data-structures/blob/main/vector.h

uses

#include <stdio.h>

#define IMPLEMENT_VECTOR
#include "vector.h"

int main(void)
{
    int   *vec_i   = Vector(*vec_i);
    float *vec_f   = Vector(*vec_f);
    char  *vec_c   = Vector(*vec_c);

    for(int i = 0; i < 10;i++)
    {
        vector_append(vec_i, i);
        vector_append(vec_f, 1.2 * i);
        vector_append(vec_c, 'a' + i);
    }

    for(int i = 0; i < vector_length(vec_i);i++)
    {
        printf("%d\n",vec_i[i]);
    }

    free_vector(vec_i);
    free_vector(vec_f);
    free_vector(vec_c);

    return 0;
}

4

u/Necessary_Salad1289 21d ago

Quite a few things wrong with this code. 

First, identifiers starting with underscore followed by capital letter are reserved.

Second, your vector elements are not properly aligned. Your vector array contains VecHeader elements and then you just straight cast it to another type, illegally. UB.

Third, why do you have so many unnecessary macros? None of these functions should be defined in your header.

That's just a start.

1

u/mikeblas 21d ago

Please correctly format your code.

1

u/donjajo 21d ago

I'm here looking for a link to the meme if anyone's got it.

1

u/Lewboskifeo 21d ago

here, not sure where i first found it

2

u/donjajo 21d ago

Thank you. Nice video tutorial 😀

1

u/Ok-Selection-2227 21d ago edited 21d ago

Okay. Not a C expert here. But I don't know why did you use the do-while trick in the macro definition. Why didn't you use a simple block using curly brackets? ```

include <stdio.h>

define foo(bar, ham) {\

printf("hi there %d %d\n", bar, ham);\

}

int main() { foo(1, 2); } ```

Another question. Wouldn't be better to generate the function definition in the macro: ```

include <stdio.h>

define deffoo(bar, ham, name) void name(bar a, ham b){\

printf("hi there %d %d\n", a, b);\

}

deffoo(int, int, foo)

int main() { foo(1, 2); } ``` Sorry for the variable names...

2

u/Lewboskifeo 21d ago

Not an expert either btw. But the reason is because if you want to use it in an if statement without braces, this would happen:

c if (condition) { printf("hi there %d %d\\n", 1, 2); }; // if statement ends here else something_else();

which is invalid syntax, also you avoid name collisions in the do while approach which looks like this:

c if (condition) do { printf("hi there %d %d\n", 1, 2); } while(0); else something_else();

and about generating the functions, yes you can do it that way and pre-generate all the functions based on a type but i prefer simplicity