C Template Library

[glouwbug]

I backported a handful of C++ STL containers to ISO C99 to exemplify that a subset of C++, namely C with Templates, is a highly usable type-safe feature within the realm of ISO C99.

Included are a couple examples, like a JSON parser and a simple 6502 compiler. I have also written a small wiki, that showcases how to use the included containers: https://github.com/glouw/ctl/wiki

[tom_mellior]

This looks cool, but I dislike the naming. Calling a queue "queue" would be so much more readable than "que", and so on. I think the everything-is-three-letters gimmick is overall a drawback. Also, would it really hurt that much to write "#define PRIMITIVE" instead of "#define P"?

[nitrogen]

This is cool! I've seen this C-with-templates used in the past with ".X" headers but haven't used the technique myself. Having something based on STL might help people to center on one library instead of constantly reinventing collections in C (which I've also done for some structures, and open sourced though I don't recommend using it: https://github.com/nitrogenlogic/nlutils).

[ummonk]

I recall a few years back doing something like this implementing a binary heap just as a hobby project (https://github.com/Equationist/ctl/blob/master/pqueue.h). I was curious to see how unoptimized it was vis a vis the STL, and ran compiled equivalent test code for both my priority queue and the STL's C++ implementation, with just integers. I was kind of shocked to find that my implementation was like 30% faster when both were compiled at -O3 levels. Seeing this backport I guess there isn't anything fancy in the STL implementations, so it's less surprising that my naive implementation could be just as fast (or happen to be faster).

[matvore]

Did you consider using more traditional macros like VEC_ADD which works for all types rather than generating e.g. vec_<type>_add? The latter approach doesn't work with cscope and ctags, which is a pretty big drawback in my book (I like it when my super trivial IDE configuration works, which is only possible with C).

See the comment and following 4 macros for how this would work with a (add-only, not growable) hashmap:

https://github.com/matvore/nusort/blob/master/src/util.h#L16...

[pjmlp]

Well, that is how BIDS 1.0 was designed, before C++ got templates.

[panta]

This is awesome! Very useful for writing highly portable software in C. I think I’ll use this library also with my students.

[apankrat]

Nice, very nice. All of it. Long live C.

Being stuck with C++ I did something in reverse - ported C-style ("intrusive") containers to ++, making them a bit safer to use, but keeping the syntax nearly the same.

https://github.com/apankrat/notes/tree/master/intrusive-cont...

[baybal2]

What do you think about Glib?

[higherhalf]

Are they fuzzed? Should be useful as some guarantee against memory-safety bugs. Didn't find this mentioned in the project.

[ku-man]

Great work! And thank you for making it available for everyone.

Did you also run tests against other libraries such as glib?

[eqvinox]

Shameless plug:

http://docs.frrouting.org/projects/dev-guide/en/latest/lists...

https://github.com/FRRouting/frr/blob/master/lib/typesafe.h

Differs in a bunch of design decisions. Memory management for items is strictly out of scope, though some of the structures use malloc/free for their own purposes (e.g. heap). Much more focus on sorted/hashed structures, explicitly differentiating for [not] having duplicate items that compare equal. Also, atomic/lock-free versions. Uses macros instead of #including files multiple times.

But fun to see someone else's go at the same idea :)

[ludocode]

Might as well plug mine too:

https://github.com/ludocode/pottery

I'm not really sure what makes a project take off on HN. I posted mine here a couple weeks ago and got one single upvote :(. I'm glad to see the new style of #include templates getting more attention though. I think in general it's the right way to do templates in C.

[optymizer]

Congrats on having an idea, coding it up and releasing it as a library! You should be proud.

Now I'd like to respectfully offer a bit of constructive criticism. Your idea is fine, but I think the API needs some polishing.

1) The 3 letter names have to go. 'vec' is somewhat is established in graphics libraries, so you might get away with that, but 'lst' - seriously? Just use 'list', 'queue', 'map', etc. Don't invent your own terms for well-known concepts. It's ok if combined data types are a bit longer. 'list_queue' is fine and very readable, 'lst_que' is less so.

2) "#define P" is clunky for several reasons: a) why do we have to care about POD vs non-POD? is it impossible to get rid of that? b) for the same reason that just using "int p" is clunky; and c) imagine lots of developers actually using your library. It would be great if each one of them didn't have to look up what "define P" is (what would google results be?). My suggestion would be to do away with having to define it

3) multiple #define in front of an #include is verbose imo. It works, but it's not perfect. I'd shoot for perfect, but that's just me. I suspect this would require significant API change so I don't have a good suggestion at the moment, I just know that I personally would not prefer multiple #define calls before I include the list. I get that you're using X-includes, but a single #define is my limit before I groan, but other people's tolerance level might be different.

Cheers!

[asveikau]

> 2) "#define P" is clunky for several reasons: a) why do we have to care about POD vs non-POD?

Because the latter needs some equivalent to a copy constructor and destructor.

I had another reaction: there is no equivalent to a move constructor? That becomes painful when it's time to support a vector of vectors. (Don't want to do a deep copy of all elements when you resize the vector.)

[CyberDildonics]

It all seems reasonable to me. Caring about shortened names is putting a lot of emphasis on something trivial. Programming gets a lot harder than that.

[leni536]

The performance of sort being exactly the same as the C++ implementation looked a bit suspicious to me at first. Notable that in the C++ performance test a function pointer is passed to std::sort in a similar way how the C library is used [1].

This is probably a good way to check that the C library doesn't do worse in this case, but it's notable that C++ has potentially faster ways to do the sorting:

1. Pass a function object (even a lambda that just wraps "compare")

2. Don't pass a comparison at all for the "vector<int>" case, as the default works there.

Both of these methods have better chances for inlining the comparison within the sort implementation. For the function pointer case it would require constant propagation and possibly "cloning" to do the same, which is less likely for a complicated algorithm like sort.

[1] https://github.com/glouw/ctl/blob/09f5e0a89d3fc621aff94290c4...

edit: I wonder how ctl's vector sort compares to qsort, I expect it to be faster.

[ludocode]

I don't believe this is correct. Passing a function name to a C++ template doesn't mean it will be called by an indirection at runtime. The compare function will certainly be inlined. Wrapping it in a lambda is useless and would at best optimize to the identical code.

[trott]

EA developers weren't happy with STL, so they created their own version, EASTL. One of their complaints had to do with custom allocators: STL allocators combine allocation and initialization.

Reading their critique of STL design decisions, as well as of their own, might be useful here: http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2007/n227...

[Alupis]

I have to admit, the STL - and more generally templates - in C++ are very perplexing to someone that has a strong background in a language with a more complete generics implementation (ie, Java or C#).

The very fact that templates are not classes, specifically not base classes for all derived variants of the template is perplexing and, in my opinion, a major swing and miss for a language that seems to pride itself on having everything including the kitchen sink.

I've read the reasons behind why templates do not share any inheritance with derived classes, and it makes sense within the context of how C++ and more specifically the compiler works... but it limits the usefulness of templates past mere containers.

[dragontamer]

> but it limits the usefulness of templates past mere containers.

Your post (specifically, your conclusion) makes me think that you are fundamentally mistaken about how to use templates.

Template metaprogramming is an old-trick at this point, with a huge variety of applications in C++. But even if you ignore Template metaprogramming (which many argue is too difficult to understand...), bog-standard C++ techniques like CRTP (Curiously Recurring Template Pattern) shows how useful templates can be outside of containers.

https://en.wikipedia.org/wiki/Curiously_recurring_template_p...

---------

C++ templates are extremely different beasts than generics. Templates are closer to a meta-language than a language feature. They hold important roles in optimization... specifically allowing you to convert "runtime code" into "compile time code" in a huge class of problems.

CRTP is a great example of retaining OOP-style polymorphism while compiling down into highly efficient non-virtual calls... with practical applications into GUI frameworks, video games and more. And its only made possible due to templates.

[slavik81]

As a C++ developer, I see things entirely the other way. Java templates are much less powerful than C++ templates. In Java, templates were basically just a convenient way to do type erasure. That's better than nothing, but the inability to specialize templates makes them quite limited. In C++, you can define a common base class if you need one, but being able to optimize based on the template type is very useful.

Function templates are great for writing concise, efficient math that handles half-precision, single-precision, double-precision, single-precision complex numbers and double-precision complex numbers (and more) with minimal duplication.

Templates are also what make interfaces like std::format efficient and easy to use.

[aw1621107]

> The very fact that templates are not classes, specifically not base classes for all derived variants of the template is perplexing

I'm a little confused at what you're trying to get at here. What do you want to do that needs such a thing? What is the equivalent Java/C# code you have in mind?

> but it limits the usefulness of templates past mere containers.

What kinds of uses did you have in mind for a "template base class"?

[teabee89]

In the wiki an int compare(int * , int * ) function [1] is used, which is odd if the elements are not pointers (when P is defined). Shouldn't it be changed to int compare(int, int) when P is defined? I wonder if it impacts at all the benchmarks.

[1] https://github.com/glouw/ctl/blob/49b90312f9473057fd2ed77941...

[glouwbug]

The compare nomenclature is a one size fits all, given larger structs require a pointer to prevent large amount of copies. Think of qsorts compare, which uses two void* arguments.

[tu7001]

Be nice to see a hash map here.

[glouwbug]

Due to popular demand, I will implement unordered_set after the holidays, once the new year is in full swing.

[daitangio]

Impressive work. I think you can use it twice in a file including it two times with redefine.

Can you provide an example with typedef and two different list types?

[glouwbug]

I imagine something along the lines of:

    typedef char* charp;
    #define P
    #define T charp
    #include <lst.h>

    typedef struct { int x, y; } point;
    #define P
    #define T point
    #include <lst.h>

    int main(void)
    {
        lst_charp a = lst_charp_init();
        lst_point b = lst_point_init();
        lst_charp_push_back(&a, "the");
        lst_charp_push_back(&a, "quick");
        lst_charp_push_back(&a, "brown");
        lst_charp_push_back(&a, "fox");
        lst_point_push_back(&b, (point) { 53, 32 });
        lst_point_push_back(&b, (point) { 11, 22 });
        lst_point_push_back(&b, (point) { 83, 23 });
        lst_charp_free(&a);
        lst_point_free(&b);
    }

[rurban]

I didn't like the names at all, and also it shouldn't be in the main namespace, but under ctl/

https://github.com/rurban/ctl

In work are map, forward_list, unordered_set, and utf-8 support for strings and identifiers, with its stricter rules.

[SurfingInVR]

This is interesting! Why not ANSI C, if not going for the latest C spec?

[glouwbug]

C99 Variadic macros, for one, which allows for a nice to use `foreach` implementation. As for the latest C spec, I use a set of C compilable by C++, since most of the functional tests back-test against the STL, and hence compile with a C++ compiler

[okaleniuk]

Ok, you can take away my C++ now :-) Seriously though, nicely done!

[backpropaganda]

How would I include the definitions without the implementations?

[notorandit]

Long live C!

[ausjke]

Looks awesome to me. Will use it in future projects. Thanks for the great work.