5 ms·

C_std: Implementation of C++ standard libraries in C

115 points by signa11 3y ago

mauvia 3y ago
I don't know if the author is looking at this comment section but small issue: > Array: Implements a dynamic array similar to std::array in C++. should read "static array". std::array requires you to state the size. C++ std::arrays are pretty much just uniformly typed tuple structures, not dynamic arrays. In fact you can use them directly on the stack with no memory allocations whatsoever.
- Arech 3y ago
  Erm, actually, all STL implementations I've seen use a simple C-style array under the hood to store `std::array` data, not a much more complex tuple. But it doesn't matter much in the context of the question: the whole point of `std::array` is to provide fixed inplace storage for the data, basically just a safe version of a C-array. Implementing it on top of dynamically sized vector, like the author did, is... just missing the whole idea. This thing was the first I noticed while looking at the sources... And I don't want to look any more further now.
  - quietbritishjim 3y ago
    I think that's what parent comment meant by "tuple": a list-like structure that can't be resized.
  - mauvia 3y ago
    Dynamically allocated static array might be closer to truth for what they implemented, I think.
- phire 3y ago
  The real std::array is static. But c doesn't really have any way to do static arrays, so c_std has decided to implement a dynamic array with an api similar to the std::array. The documentation is correct regarding what c_std has actually implemented. And it's still useful, unlike vector the size is (dynamically) set once at construction and then enforced.
  - jenadine 3y ago
    Of course C can do static array: int array[N]; is one.
    - quietbritishjim 3y ago
      But not an abstract data structure that can be allocated on the stack. (Your example can go on the stack. A struct with a final array member of unspecified size can work as an abstract data structure. But you can't have both at once.)
  - mauvia 3y ago
    Well, std::array is meant to be a direct replacement for what jenadine mentioned, the C style of doing static arrays. I think under the hood it takes over the array initialization syntax as well (or array initialization of objects got added to the standard to support std::array?) and IIRC there are some functions that are simply unavailable to std::array because of its array based construction. I don't remember exactly what but I have run into it before, I think the iterator implementation is a raw pointer and that breaks the interface expectations a bit?
dig1 3y ago
Great work! I always liked the simplicity of C and the neat design of STL. After some quick sneak peeks, I'd suggest allowing the user to set up a custom memory pool and/or allocator (malloc/free). These could be set via additional pointers (with a small overhead) or allowed via ifdefs in compile time so that we can opt for fast or flexible options. Good luck with future development :)
zabzonk 3y ago
i took a brief look at the csv module (i know quite a bit about csv - authpr of the csvfix tool) and i would observe one general point. the error handling is terrible. functions either call exit() on an error, or simply print an error message and carry on as if nothing was wrong. i know error handling in C is difficult (one reason i prefer C++) but we can do better than this. another general point is that almost all the functions return void. this means that they must have side-effects. i am very far from being an FP maniac, but i do like a bit of purity when i can get it. also, some comments would be nice. bottom line - not for me, but then i haven't written any C for over 30 years :-)
- vitosartori 3y ago
  That's a huge pain point, but I'm curious! What would be a good approach in your opinion? I'm not questioning the exit/print error and carry on, that's plainly wrong. When working on private projects/libs, my functions usually return an enum error type, and do all data handling - be it arguments or returns - through pointers passed as args; I mean, I think that's the usual convention, but you clearly have way more experience, so I thought about asking! :) Looking at you, syscall!
  - zabzonk 3y ago
    well, i guess in C you should return a value indicating the error probably via a struct that contains the error and the success data. C programmers seem to have a terrible aversion to returning structs (possibly they don't realise that you can do it?) where in other value-based languages (e.g. c++, go) it is very common. of course, there are reasons for mucking around with pointers. but down that route lies pointers-to-pointers, and eventually madness.
  - Const-me 3y ago
    On Windows, this problem is already solved well. Return 32-bit integers which conform to that spec: https://learn.microsoft.com/en-us/openspecs/windows_protocols/ms-erref/0642cb2f-2075-4469-918c-4441e69c548a https://learn.microsoft.com/en-us/openspecs/windows_protocol... Possible to pack OS errors, third party library specific errors, and other classes of errors into a single value. Technically, you can implement that spec for all OSes. I did a few times, defining vendor-specific facilities for Linux components I used, like xwindows, drm/kms, etc..
mgaunard 3y ago
While it takes some inspiration from the naming of the C++ standard library, it's done so inconsistently, and the implementation is pretty much nothing like it. It's just a C framework, and not nearly as high quality as say, Glib.
- nolist_policy 3y ago
  +1 for Glib if you are looking for a good C "standard" library.
lionkor 3y ago
There are various projects posted here and on other platforms which do this kind of thing (DSA stuff in C). What baffles me is the lack of any tests here. I understand writing tests is boring, and I understand writing tests in C is the least fun writing tests could be, but: I was thinking how neat this is and how I was going to use this for my own projects, until I saw it has no tests. C is one of the few languages where, unless you're formally verifying it on paper, you need static analysers, dynamic analysers, and unit tests, all at the same time, to make sure your programs pass the bare minimum stability required to be used.
max_k 3y ago
The author contacted me via email yesterday (because they saw I'm writing a lot of C++ code on GH) and asked me for a review. This was my somewhat-grumpy somewhat-trollish reply: Your library demonstrates that C++ is the superior language because it can to template specialization, resulting in better machine code. For example, your std::span implementation needs to store the element size, resulting in a larger structure (24 instead of 16 bytes), more memory memory accesses, costly integer multiplications everywhere. C++ can omit all this, and can do simple bit shifts instead of multiplications. There are many more places where you demonstrate C++'s superiority (e.g. it can safely do deep copies with no special code, while your library can't do copies at all, and even if it could, doing so safely/deeply would be extremely cumbersome with C, both for your library code AND for the code calling your library; all a piece of cake in C++). Oh, and "Implements a dynamic array similar to std::array" .... that's factually wrong. std::array is not a dynamic array. std::vector is. Interestingly, your std::array implementation uses your std::vector, while adding some more runtime overhead. Hey, it's C, it's slower than C++ is what I learn again here! It's a rather pointless library, unless your point is to demonstrate that C is a bad programming language.
- Matheus28 3y ago
  The tuple implementation is also nasty in how much memory in allocates. It's the only one I looked at, to be honest.
- nextaccountic 3y ago
  Do you have anything good to say about it?
  - max_k 3y ago
    Maybe I could say something good about some aspects of their coding style, but that would only distract from my main point that I find it pointless to imitate a C++ API in C, when that API is modeled carefully to take advantage of C++ features, and you lose all of that in C. (Not only that - their C API is designed in a way that adds overhead even where none would be necessary in C, by allocating all structs on the heap.) There are lots of plain C container libraries which are probably suited better for C, if you really must use C, or prefer C for whatever reason that escapes my imagination.
feverzsj 3y ago
That's why I support the linux C++ patch. [0] https://www.phoronix.com/news/CPP-Linux-Kernel-2024-Discuss https://www.phoronix.com/news/CPP-Linux-Kernel-2024-Discuss
harha_ 3y ago
Looks very nice! Whenever I write hobby stuff in C, I re-implement (for fun) simple stuff such as a dynamic vector, dynamic string and a key-value map, but nothing to this extent ofc.
properparity 3y ago
Vector* vector_create(size_t itemSize) { Vector* vec = (Vector*)malloc(sizeof(Vector)); // ... return vec; } This just immediately strike me as poor code. C is not java, you do not have to "new" up every little structure. void vector_init(Vector *v, size_t itemSize) { v->itemSize = itemSize; // ... } Instantly cleaner, more efficient, less memory allocation/handling needed, lets the user control where the Vector is stored.
- deleted 3y ago
  [deleted]
- gpderetta 3y ago
  Assuming that vector is just a dataptr/size/capacity triplet, vector create can just return by value.
- pjmlp 3y ago
  The new operator in Java doesn't always heap allocate, it depends on the JIT and escape analysis, it might be stack/register allocated if proven safe to do so.
deleted 3y ago
[deleted]
Decabytes 3y ago
I hope the author continues to work on this. The C++ standard lib has been worked on for decades so expecting this iteration to be at feature parity is silly. The feedback here will help make it better. It would be nice for C to have this

115 points by signa11 3y ago

I don't know if the author is looking at this comment section but small issue: > Array: Implements a dynamic array similar to std::array in C++. should read "static array". std::array requires you to state the size. C++ std::arrays are pretty much just uniformly typed tuple structures, not dynamic arrays. In fact you can use them directly on the stack with no memory allocations whatsoever.

Arech 3y ago
Erm, actually, all STL implementations I've seen use a simple C-style array under the hood to store `std::array` data, not a much more complex tuple. But it doesn't matter much in the context of the question: the whole point of `std::array` is to provide fixed inplace storage for the data, basically just a safe version of a C-array. Implementing it on top of dynamically sized vector, like the author did, is... just missing the whole idea. This thing was the first I noticed while looking at the sources... And I don't want to look any more further now.
- quietbritishjim 3y ago
  I think that's what parent comment meant by "tuple": a list-like structure that can't be resized.
- mauvia 3y ago
  Dynamically allocated static array might be closer to truth for what they implemented, I think.
phire 3y ago
The real std::array is static. But c doesn't really have any way to do static arrays, so c_std has decided to implement a dynamic array with an api similar to the std::array. The documentation is correct regarding what c_std has actually implemented. And it's still useful, unlike vector the size is (dynamically) set once at construction and then enforced.
- jenadine 3y ago
  Of course C can do static array: int array[N]; is one.
  - quietbritishjim 3y ago
    But not an abstract data structure that can be allocated on the stack. (Your example can go on the stack. A struct with a final array member of unspecified size can work as an abstract data structure. But you can't have both at once.)
- mauvia 3y ago
  Well, std::array is meant to be a direct replacement for what jenadine mentioned, the C style of doing static arrays. I think under the hood it takes over the array initialization syntax as well (or array initialization of objects got added to the standard to support std::array?) and IIRC there are some functions that are simply unavailable to std::array because of its array based construction. I don't remember exactly what but I have run into it before, I think the iterator implementation is a raw pointer and that breaks the interface expectations a bit?

dig1 3y ago

Great work! I always liked the simplicity of C and the neat design of STL. After some quick sneak peeks, I'd suggest allowing the user to set up a custom memory pool and/or allocator (malloc/free). These could be set via additional pointers (with a small overhead) or allowed via ifdefs in compile time so that we can opt for fast or flexible options. Good luck with future development :)

zabzonk 3y ago

i took a brief look at the csv module (i know quite a bit about csv - authpr of the csvfix tool) and i would observe one general point. the error handling is terrible. functions either call exit() on an error, or simply print an error message and carry on as if nothing was wrong. i know error handling in C is difficult (one reason i prefer C++) but we can do better than this. another general point is that almost all the functions return void. this means that they must have side-effects. i am very far from being an FP maniac, but i do like a bit of purity when i can get it. also, some comments would be nice. bottom line - not for me, but then i haven't written any C for over 30 years :-)

vitosartori 3y ago
That's a huge pain point, but I'm curious! What would be a good approach in your opinion? I'm not questioning the exit/print error and carry on, that's plainly wrong. When working on private projects/libs, my functions usually return an enum error type, and do all data handling - be it arguments or returns - through pointers passed as args; I mean, I think that's the usual convention, but you clearly have way more experience, so I thought about asking! :) Looking at you, syscall!
- zabzonk 3y ago
  well, i guess in C you should return a value indicating the error probably via a struct that contains the error and the success data. C programmers seem to have a terrible aversion to returning structs (possibly they don't realise that you can do it?) where in other value-based languages (e.g. c++, go) it is very common. of course, there are reasons for mucking around with pointers. but down that route lies pointers-to-pointers, and eventually madness.
- Const-me 3y ago
  On Windows, this problem is already solved well. Return 32-bit integers which conform to that spec: https://learn.microsoft.com/en-us/openspecs/windows_protocols/ms-erref/0642cb2f-2075-4469-918c-4441e69c548a https://learn.microsoft.com/en-us/openspecs/windows_protocol... Possible to pack OS errors, third party library specific errors, and other classes of errors into a single value. Technically, you can implement that spec for all OSes. I did a few times, defining vendor-specific facilities for Linux components I used, like xwindows, drm/kms, etc..

mgaunard 3y ago

While it takes some inspiration from the naming of the C++ standard library, it's done so inconsistently, and the implementation is pretty much nothing like it. It's just a C framework, and not nearly as high quality as say, Glib.

nolist_policy 3y ago
+1 for Glib if you are looking for a good C "standard" library.

lionkor 3y ago

There are various projects posted here and on other platforms which do this kind of thing (DSA stuff in C). What baffles me is the lack of any tests here. I understand writing tests is boring, and I understand writing tests in C is the least fun writing tests could be, but: I was thinking how neat this is and how I was going to use this for my own projects, until I saw it has no tests. C is one of the few languages where, unless you're formally verifying it on paper, you need static analysers, dynamic analysers, and unit tests, all at the same time, to make sure your programs pass the bare minimum stability required to be used.

max_k 3y ago

The author contacted me via email yesterday (because they saw I'm writing a lot of C++ code on GH) and asked me for a review. This was my somewhat-grumpy somewhat-trollish reply: Your library demonstrates that C++ is the superior language because it can to template specialization, resulting in better machine code. For example, your std::span implementation needs to store the element size, resulting in a larger structure (24 instead of 16 bytes), more memory memory accesses, costly integer multiplications everywhere. C++ can omit all this, and can do simple bit shifts instead of multiplications. There are many more places where you demonstrate C++'s superiority (e.g. it can safely do deep copies with no special code, while your library can't do copies at all, and even if it could, doing so safely/deeply would be extremely cumbersome with C, both for your library code AND for the code calling your library; all a piece of cake in C++). Oh, and "Implements a dynamic array similar to std::array" .... that's factually wrong. std::array is not a dynamic array. std::vector is. Interestingly, your std::array implementation uses your std::vector, while adding some more runtime overhead. Hey, it's C, it's slower than C++ is what I learn again here! It's a rather pointless library, unless your point is to demonstrate that C is a bad programming language.

Matheus28 3y ago
The tuple implementation is also nasty in how much memory in allocates. It's the only one I looked at, to be honest.
nextaccountic 3y ago
Do you have anything good to say about it?
- max_k 3y ago
  Maybe I could say something good about some aspects of their coding style, but that would only distract from my main point that I find it pointless to imitate a C++ API in C, when that API is modeled carefully to take advantage of C++ features, and you lose all of that in C. (Not only that - their C API is designed in a way that adds overhead even where none would be necessary in C, by allocating all structs on the heap.) There are lots of plain C container libraries which are probably suited better for C, if you really must use C, or prefer C for whatever reason that escapes my imagination.

feverzsj 3y ago

That's why I support the linux C++ patch. [0] https://www.phoronix.com/news/CPP-Linux-Kernel-2024-Discuss https://www.phoronix.com/news/CPP-Linux-Kernel-2024-Discuss

harha_ 3y ago

Looks very nice! Whenever I write hobby stuff in C, I re-implement (for fun) simple stuff such as a dynamic vector, dynamic string and a key-value map, but nothing to this extent ofc.

properparity 3y ago

Vector* vector_create(size_t itemSize) { Vector* vec = (Vector*)malloc(sizeof(Vector)); // ... return vec; } This just immediately strike me as poor code. C is not java, you do not have to "new" up every little structure. void vector_init(Vector *v, size_t itemSize) { v->itemSize = itemSize; // ... } Instantly cleaner, more efficient, less memory allocation/handling needed, lets the user control where the Vector is stored.

deleted 3y ago
[deleted]
gpderetta 3y ago
Assuming that vector is just a dataptr/size/capacity triplet, vector create can just return by value.
pjmlp 3y ago
The new operator in Java doesn't always heap allocate, it depends on the JIT and escape analysis, it might be stack/register allocated if proven safe to do so.

deleted 3y ago

[deleted]

Decabytes 3y ago

I hope the author continues to work on this. The C++ standard lib has been worked on for decades so expecting this iteration to be at feature parity is silly. The feedback here will help make it better. It would be nice for C to have this