C Template Library
github.com
github.com
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
Did you also run tests against other libraries such as glib?
As for your pqueue implementation, the efficacy of an optimizing compiler lies in the inherent complexity of the language. I can imagine the optimization backend for gcc is simpler (and more effective) than g++, but I am not an expert on compiler internals.
And I've written similar things myself (hash table and vectors).
I wanted a good hash map, so I spend a lot of time comparing them. There are like 10 separate map implementation in FreePascal, but they are all slower than C++'s std::unordered_map.
Then I compared another dozen of libraries, and found the fastest one that is like 50% faster than std::unordered_map. But it was a rather straight forward implementation of non-linear open addressing.
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...
https://www.boost.org/doc/libs/1_75_0/doc/html/intrusive.htm...
Have you considered it? Is it deficient for your use case?
"the goal here is to make a better version of C-style containers rather than to implement something C++-style and similar,"?
But a goal is not a reason. I.e. why doing
CONTAINER_OF( user_data, vip );
container_of<&user_data::vip> vip_list;
As to why to do what you wrote I have no idea. These two code snippets are unrelated.
If I were to pick the reason, it'd be simply that I don't like Boost.
To me, Boost is an ultimate embodiment of all that went wrong with C++ when it evolved from being a better version of C into the multi-paradigm monstrosity that it is now. Just look at the man page linked above. How to get a clever little concept of intrusive containers and completely decimate it into a technically correct, but unpalatable formulistic piece of engineering that, above all else, is rid of any shred of elegance that made the original concept so great in the first place.
It will also take up more space, to store that very pointer.
All of which starts to matter (a lot) when operating with very large data sets.
Among other implications (different memory locality and allocation guarantees), you could have the same intrusive node object used in several container objects or even classes (though not at the same time). That is, pull an element from a doubly linked list and insert it into a binary tree without reallocation.
With std::list you need to find the iterate to the node before you can delete it.
Many things have exactly one correctly spelled full name, but many alternative contractions or cute variations.
Programmers can be expected to know the correct spelling of "vector" or "dequeue". They can't be expected to know your specific contraction or abbreviation of it. They can't guess and they're not mind readers. They have a muscle memory that has them type out the full word automatically, without thinking.
Don't break these expectations.
Yes.
https://www.npmjs.com/package/dequeue
https://api.jquery.com/dequeue/
https://docs.microsoft.com/en-us/dotnet/api/system.collections.generic.queue-1.dequeue?view=net-5.0https://doc.rust-lang.org/std/collections/struct.VecDeque.ht...
EQ/EQL/EQUAL/EQUALP, PROCLAIM/DECLAIM/DECLARE, and the atrocious PAIRLIS (really??). And not to mention the fact that PAIRLIS returns an association list, which is entirely different from a "plist".
And then of course CAR, CDR, CADR, CDDR, et alia.
This is all second nature for an experienced Lisp programmer, but it makes for a difficult learning experience.
I hate this field so much. That anyone creative chooses willingly to go into software is a miracle. Are there people out their with pre-broken spirits, that want to join this soul-less galley of horrors? Starvation should be preferable to this. But i digress..
Why not make naming something that can be personalized? Make the variablename a sort of rule-based-building-block-lego-system, that can be adapted by the user.
Increment+Variable -> "upIndex" for you Increment+Variable -> "incVar" for me. Everyone is happy, the frameworks and apis only specify the buildingblocks as variableNames.. autotranslated variableNames, customized to everyones flavour.
Hooray, i contributed. Prolonging the nightmare.
I'm not sure which way is more popular. Paul Graham has mentioned in several essays how programmers are lazy and want to type the minimum number of characters possible. On the other hand Elon Musk has loudly complained about acronyms and contractions.
In the end you can't please everyone, so the developer just has to pick a style and go with it. If you dislike the short names, it's easy enough to put a comment above the template instantiation explaining what's going on.
Not as elegant as some IDEs I'm sure, but if typing is stopping you from using longer names, this could help.
I do actually agree on the primitive vs p thing though...
(I have worked on code where the debug print macro was called P...)
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...
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 :)
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.
Pottery's intro_sort has comparable or better performance to swenson's quick_sort but with a lot more features. You can supply a move or swap expression to Pottery to swap non-bitwise-movable types, you can supply array access expressions to sort non-contiguous arrays, and it has the heapsort fallback to guarantee O(nlogn) performance.
I don't have a Timsort yet though. For that, swenson's implementation is surely the best.
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!
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.)
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.
edit: In this talk this exact scenario is analysed in depth:
I don't think it matters in this benchmark though. Compilers can certainly deduce that it's a compile-time constant because the template is fully instantiated in the same translation unit and only used once so it's not hard for a compiler to propagate it. At least in my tests GCC and Clang seem to propagate it just fine.
I suppose a case where it might matter would be if you call std::sort several times in the same translation unit (or the same binary under LTO) with the same template types but different comparison functions. In that case calls to std::sort with different comparison functions would share an implementation so it couldn't be inlined.
You're right though, it should be fixed. Rather than making it a lambda, the benchmark probably shouldn't pass a compare expression to std::sort at all so it can make its own decisions on how to compare values. For example I expect C++20 implementations of std::sort may provide alternate implementations of partitioning that use the spaceship operator if it exists (at least my implementation will.) This is one of the true advantages C++ has that can't be replicated in C.
Inlining pointers requires doing constant propagation and the compiler can give up if it has to track too much stuff, while in the lambda case, the type of the comparator is always available.
Also lambdas can be removed in the early inliner stage exposing them to more optimization opportunities, while function pointers have to be inlined after constant propagation.
As usual, it is a trade off, so there is no substitute to measuring in your specific scenario.
In my tests gcc clones sort and inlines the comparison only in -O3. clang doesn't do it even with -O3, neither with libstdc++ nor libc++.
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...
That being said, I’ve never found the STLs use of initialized allocation to be a problem, but I don’t work in game design.
But the criticism is still questionable: an allocator can define ::construct() not to do anything, and leave actual construction to user code.
A few more of the criticisms are addressed in C++11 which fully support stateful allocators; they were not mandated (but still allowed) in C++03 because some implementors felt that the STL was too much work to implement already.
Most of the rest are QoI issues, and it is perfectly reasonable for EA to have its own STL implementation that give the same guarantees across platforms, but it is not a criticism of the standard itself.
Isn't initalising an optional basically a trivial operation? The default constructor is fundamentally the equivalent of setting a boolean flag to 0.
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.
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.
I do "get it" that templates are not generics... there's just a lot of gotchas for someone assuming generics, err - templates are similar to other languages. Like the difficulty in nesting templates in templates...
Java / C#'s concept of "Everything derives from Object" is outright rejected in C++. Templates are part of this culture: how can we provide extendibility when nothing is an Object?
Well, look at iterators in C++. All C++ iterators extend from all collections WITHOUT the use of OOP-derivations. That's thanks to the magic of Templates.
------
What's going on? C++ templates allow the creation of new iterator classes. It invokes the compile-time language to create a new class at compile time.
In Java / C#: vector<MyClass> is the same old vector as all other vectors.
In C++: vector<MyClass> is a custom-made, completely separate class from all other vectors. vector<MyClass>::iterator is a 2nd, custom-made completely separate class from all other iterators.
And yet, all of these different classes can be used the same, thanks to the use of auto, or other compile-time structures in C++.
void myFunc(List<? extends MyDataContainer<?>> list);
C++ templates may be very powerful, but limitations like this feel out of place in a language as bloated as C++ already is...
Admittedly, I still have much to learn about C++. It's been quite an experience, frustrating at times, learning this language.
template<typename T, typename U>
void my_func(std::vector<T>* vec) requires std::derived_from<T, my_data_container<U>>;
Without concepts, you're left with SINFAE:
template<typename T, typename U, typename = std::enable_if_t<std::is_base_of_v<my_data_container<U>, T>>>
void my_func(std::vector<T>* vec);
template<typename T, typename U>
void my_func(std::vector<T>* vec) {
// use my_data_container<U> somewhere and hope things blow up if something is wrong
// Not 100% sure this is allowed, but something similar should be at least
}EDIT: Remember, in C++, "BaseClass" cannot polymorph, only "BaseClass * " can. (BaseClass is where the data is stored precisely. If its 20 bytes of RAM, then DerivedClass might be 24 bytes of RAM, and therefore can't fit. But both BaseClass * and DerivedClass * are compatible with each other, and may convert into each other, as long as you know the pointer goes to the right kind of class)
And if that's not sufficient, then a static_assert over the type information is probably what you need. Ex:
template<class T>
void myFunc(List<T> list){
static_assert(std::is_nothrow_convertible(T, BaseClass)); // I haven't tried, but this probably works
}
In this case, we've created a static_assert (aka: a compile-time error will pop up) if T does not convert into BaseClass (note: T may have a CopyConstructor(BaseClass), so maybe its not exactly tthe same concept as what you're trying to do... but this gives you an idea of C++isms...)
Well, nothing I suppose, except BaseClass cannot then be a template, and you cannot have derived class-specific return types like a template would allow.
So, having BaseClassInt type return int from some function but BaseClassLong return a long gets more challenging than it should be. (I recognize all my examples so far had a void return type, that was just for simplicity).
> But both BaseClass * and DerivedClass * are compatible with each other, and may convert into each other, as long as you know the pointer goes to the right kind of class)
Which loses type safety, unfortunately.
> In this case, we've created a static_assert (aka: a compile-time error will pop up) if T does not convert into BaseClass
I'll look into the static_assert() option, could prove useful in some cases.
At the end of the day, there are two things at play here - my lack of C++ familiarity, and in some cases it's just how C++ is.
It is a strange feeling though, having a language limit your expressiveness for the first time...
template <class T>
void myFunc(List<T*>){
static_assert(stuff about T that you want to guarantee at compile time);
}
For a list of common functions used for compile-time type checking.
Few other programming languages offer a similar feature. C++ pulled it off with an ISO standard and multiple conformant implementations.
Templates are loved by many, but they are a contender (along with UB) for the most hated C++ feature due to complexity.
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"?
The two resulting derived classes are not the same, and you cannot have a function that accepts the base template with a wild card type and pass both types into it.
In Java, you can do: void myFunc(List<?> list); and all List objects with any type can be accepted by this method, in addition any class that extended List can also be accepted into this method, such as ArrayList<?> or whatever.
As far as I've seen, this is impossible in C++, unfortunately.
template<typename T>
void my_func(std::vector<T>& vec);
The reference (or use a pointer, if you want) ensures that derived types can be passed, and the template allows for any parameterization to be used.
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.
[1] https://github.com/glouw/ctl/blob/49b90312f9473057fd2ed77941...
> STL std::map will not be implemented in CTL because maps only provide slight syntactic improvements over sets.
makes no sense to me.
It's the other way around: a set is a map with a irrelevant / ignored value (or singleton / ZST if available), with built-in functions for set-oriented operations (union/difference/subset/superset/disjoint). So if you're only going to provide one of them, you provide a map (that's what Go does).
You don't have to implement sets in terms of maps though, it can be useful to provide different implementations of them as their usage patterns can be different and thus it might make sense to use a different underlying data structure (not sure about trees there but definitely a possible consideration for hashes).
It also makes sense to have a bespoke set implementation if the language doesn't have ZSTs, to avoid wasting space (between 1 byte and 1 word per key depending on the storage details).
Finally it can make sense to have a bespoke set implementation due to language visibility rules, so you can e.g. hit the hashes directly (rather than have to recompute them) when performing operations involving multiple sets.
This maps directly to the relational model, where a table (or relation) being a set of tuples is the fundamental concept: for your typical programming language set the uniqueness constraint (and key), would be comprised by all the columns, while for a map it would only be comprised by a subset (just one at the limit), while the remaining columns would be the mapped type.
Set operations (union, intersection, difference) do make sense for maps as well in fact.
Given a powerful enough language, you can generalize your sets and maps with multiple uniqueness constraints and secondary indices. See boost.multindex for example.
edit: and BTW, most STL implementations use the same underlying implementation for std::set and std::map which has a set-like interface with the ability to specify the key mapping function.
* Comparisons don't have to use all members of the type e.g. if I have two Employee objects then I'm allowed to create a comparison function that only compares their employee IDs and ignores the name fields (perhaps because the name ought to be derived from employee ID). (I know this article is not about C++, but as a reference point this has always been possible in C++'s STL.)
* Comparisons don't need a full-blown instance of the contained type e.g. in our employee example, the set can make use of a comparison function between int and Employee without having to construct an Employee with that ID. (This has been possible in C++ since C++11, and is often called heterogeneous lookup.)
* The last point is a bit fiddly: Either the set type allows mutation of the objects so long as the parts relevant to comparison don't change, or you only wanted to store const values anyway. I mention this because in C++ if you have a std::set<Foo> then you can't mutate the Foo elements at all, even if it has no effect on the comparison of the elements with other elements. (Unless there are const methods that actually mutate it... yuck!)
So long as you have those three things, you can have a set of (key, value) pairs where the comparitor only compares keys, and bingo you have a mapping type.
It's more straightforward to combine these templates: make map the fundamental type, but make values contain their keys and make the key type default to the value type if omitted. This way it's both a map and a set. My own C hash table template does it this way [1]: it stores only a value type and not keys, but there is an optional separate key type used for lookups, hashes and comparisons. To make it a map, you provide both a key comparison expression and an expression to convert values to keys.
[1]: https://github.com/ludocode/pottery/tree/master/include/pott...
> It's straightforward
It's really not. Straightforward is the other way around, this is convoluted and involved. It makes the library much harder to use for rather limited gains.
> Either the set type allows mutation of the objects so long as the parts relevant to comparison don't change
This sounds like a footgun requirement at best, I'm pleasantly surprised (for once) that C++ doesn't just let you mutate the entire thing at will.
Can you provide an example with typedef and two different list types?
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);
}(I scrolled through it and assumed you'd just do "#define lst list_charp"?)
Although if you're interested in just a batch rename, it's something like this:
#define vec_char str
#define P
#define T char
#include <vec.h>In work are map, forward_list, unordered_set, and utf-8 support for strings and identifiers, with its stricter rules.
https://devblogs.microsoft.com/cppblog/c11-and-c17-standard-...
#define foreach(container, variable, iterator) \
for (JOIN(container, it) iterator = JOIN(JOIN(container, it), each) (variable); \
!iterator.done; iterator.step(&iterator))
EDIT: Done, and thank you so much - it's so much cleaner this way