Implementing C++ STL containers in pure C — what I learned
Posted by springnode@reddit | programming | View on Reddit | 10 comments
[removed]
Posted by springnode@reddit | programming | View on Reddit | 10 comments
[removed]
excitius@reddit
For your vector example, I didn't look much into the implementation but the caller receives a handle into the vector's data pointer directly and can use that to index into the vector, the metadata is stored before index 0.
I didn't look at the implementation but std::vector does dynamic reallocation of the vector as size increases. The data pointer would surely be invalidated after a couple of push backs in which the size exceeds the capacity, no?
Yeah you can call realloc but there's no guarantee that the pointer is the same. I dont see anywhere in the example where the caller's handle is updated
emodario@reddit
I checked the code, and
push_back(v, ...)is a macro that, under the hood, really doescstl_push_back(&v, ...). The realloc logic is handled here for a vector.excitius@reddit
I see, that's quite invisible. I guess it does a good job abstracting the details from you like a C++ class would. Just have to make sure not to copy the handle or anything.
evaned@reddit
Minor nit, but I'd always suggest promoting
sizeof(*v)orsizeof(v[0])here.This was kind of discussed in another comment, but I think the magical dereference of the first parameter is too surprising, and I feel like it might lead to some obnoxious compiler errors if someone puts a non-lvalue there.
You're in a language without references, and I think the problems that faking them cause are worse than the "disease" of requiring the user to type &.
You don't give an example of this, but looking at the code it looks like this returns a
void*, and the same for other things. For example, I tried changingint *it = rbegin(d)todouble *it = rbegin(d)to see if I was missing something and you'd get a compiler error, but becauserbeginjust returnsvoid*, no error.Personally, I consider this a fatal flaw of the technique vs a templating library that stamps out names that have types included (e.g. something like
map_int_rbegin), though it may be fundamental to the design decisions that you want, like wanting to use unadorned names. But my feeling is that if you want that level of syntactic convenience, then... use a different language. You're using C, so accept what C does well and poorly, and this is not something it does well.The company I work for has a lot of C code that uses container classes that are generated by preprocessor, and those get adorned names.
Another benefit of adorning your names like this is that I suspect that very very few substantive C programs would have no conflict with some of the preprocessor macros you name, especially something like
size. I guess maybe those are likely to be benign conflicts in general... but enjoy the error messages and debugging experiences when common names like that get overwritten.While I'm at it, it was only when I was writing a couple paragraphs up that I realized that
int *is a weird return type to get from a map iteration, and I found that very surprising. Not wrong exactly, but if you're aiming for such closeness because it's what the STL does, it's... weird.Next up stemming from this example is that... in terms of the concrete implementation, a couple of things give me major pause. First, even this single example has a basic bug in it, with
printf("Number of elements: %d\n", len);. I'm not even asking GCC for extra warning flags, and I'm getting a warning about it. C is a serious and error-prone language. If you're this cavalier with getting types wrong and/or about going "yeah, this UB is fine", why should I have trust in the rest of your implementation?Speaking of UB, all your
__blahnames are reserved to the implementation and also technically cause UB just by being compiled into a program. I'm a bit more sanguine about this one, but it's still bad form.GasterIHardlyKnowHer@reddit
OP's post is AI generated, you're wasting your time.
GasterIHardlyKnowHer@reddit
AI slop.
evaned@reddit
Another note of feedback that I noticed:
These are bad names, especially if you're mimicing the STL. The STL also has
nextandprevbut they do something different. (They return the following iterator, but don't mutate the argument.)The STL also has a function that behaves (almost) like your
nextthough,std::advance; that is the name you should use. You probably want to make that variadic too so thatadvance(it)behaves likeadvance(it, 1)which isn't supported by the STL, but I think that would be a good enhancement. I think you'll also want to come up with a name foradvance(it, -1)(what yourprevdoes), but nothing strikes me as super great.cscottnet@reddit
Tag before pointer is an old trick. It will often confuse tools like valgrind and conservative allocators, but it usually works fine. As you noted, one benefit is easier array indexing. My recollection is that it was also used for double dispatch or a form of multiple inheritance: one method table was on positive offsets and another method table was on negative offsets. Some java implementations used positive offsets for class inheritance and negative offsets for interface inheritance, eg.
skinnybuddha@reddit
It would be interesting to compare this with the initial macro based C++ implementations which I believe existed in the cfront days of C++
AutoModerator@reddit
r/programming is not a place to post your project, get feedback, ask for help, or promote your startup.
Technical write-ups on what makes a project technically challenging, interesting, or educational are allowed and encouraged, but just a link to a GitHub page or a list of features is not allowed.
The technical write-up must be the focus of the post, not just a tickbox-checking exercise to get us to allow it. This is a technical subreddit.
We don't care what you built, we care how you build it.
I am a bot, and this action was performed automatically. Please contact the moderators of this subreddit if you have any questions or concerns.