13 ms·

C Template Library

266 points by glouwbug 6y ago

SurfingInVR 6y ago
This is interesting! Why not ANSI C, if not going for the latest C spec?
- glouwbug 6y ago
  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
  - souprock 6y ago
    You're missing out on _Generic, _Static_assert, and restrict. https://devblogs.microsoft.com/cppblog/c11-and-c17-standard-support-arriving-in-msvc/ https://devblogs.microsoft.com/cppblog/c11-and-c17-standard-...
  - smlckz 6y ago
    You do not need variadic macros! #define foreach(container, variable, iterator) \ for (JOIN(container, it) iterator = JOIN(JOIN(container, it), each) (variable); \ !iterator.done; iterator.step(&iterator)) Is this less nice? I personally do not like dangling )'s [I did not have to write DOS batch scripts :D]
    - glouwbug 6y ago
      Amazing, I can drop the variadic macro. EDIT: Done, and thank you so much - it's so much cleaner this way
      - smlckz 6y ago
        You're welcome. And you might like to see ''sys/queue.h'': https://github.com/openbsd/src/blob/master/sys/sys/queue.h https://github.com/openbsd/src/blob/master/sys/sys/queue.h
glouwbug 6y ago
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 https://github.com/glouw/ctl/wiki
- baybal2 6y ago
  What do you think about Glib?
- ku-man 6y ago
  Great work! And thank you for making it available for everyone. Did you also run tests against other libraries such as glib?
- nitrogen 6y ago
  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 https://github.com/nitrogenlogic/nlutils).
- ummonk 6y ago
  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 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).
  - 6y ago
tu7001 6y ago
Be nice to see a hash map here.
- glouwbug 6y ago
  Due to popular demand, I will implement unordered_set after the holidays, once the new year is in full swing.
  - a-dub 6y ago
    hooray for hashes!
  - MrBuddyCasino 6y ago
    In the Java stdlib, Set is implemented on top of HashMap. I don't see how the opposite is possible?
    - glouwbug 6y ago
      Sets (and maps) are implemented as red black trees in the STL. The STL unordered_set (and unordered_map) is what I believe Java would call a HashMap, unless I am mistaken (I am not a Java guru).
      - masklinn 6y ago
        I don't know that the STL requires rbtrees for map and set, but you're correct that `std::unordered_map` is the STL's hashmap. The Java version of std::map would be java.util.TreeMap (and std::set => java.util.TreeSet).
        tom_mellior 6y ago
        The STL's complexity requirements pretty much dictate a balanced binary search tree as the underlying representation for map and set. The choice then is essentially between red-black trees and AVL trees.
    - 6y ago
deleted 6y ago
[deleted]
notorandit 6y ago
Long live C!
eqvinox 6y ago
Shameless plug: http://docs.frrouting.org/projects/dev-guide/en/latest/lists.html http://docs.frrouting.org/projects/dev-guide/en/latest/lists... https://github.com/FRRouting/frr/blob/master/lib/typesafe.h 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 6y ago
  Might as well plug mine too: https://github.com/ludocode/pottery 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.
  - eesmith 6y ago
    FWIW, for sorting in a template-like C package I use https://github.com/swenson/sort/ https://github.com/swenson/sort/ .
    - ludocode 6y ago
      That library is included in Pottery's benchmarks! :) It's another of the very few C libraries that use the #include template style. 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.
      - 6y ago
daitangio 6y ago
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 6y ago
  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); }
  - eqvinox 6y ago
    Wait ... "imagine" - you can't currently do more than one? That's kind of the essential point with templates. (I scrolled through it and assumed you'd just do "#define lst list_charp"?)
    - gpderetta 6y ago
      it seems that it "instantiates" two list types: lst_charp and lst_point and uses both of them. What's the issue?
      - deleted 6y ago
        [deleted]
    - wffurr 6y ago
      “Imagine” as in that code is written in an HN comment, not a C source file, and probably hasn’t been checked with a compiler yet. Why don’t you copy and paste it into a test, try it out, and report back?
blargmaster42_8 6y ago
God the macro bs..and your people have tha audacity to complain about C++....
okaleniuk 6y ago
Ok, you can take away my C++ now :-) Seriously though, nicely done!
deleted 6y ago
[deleted]
leni536 6y ago
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/09f5e0a89d3fc621aff94290c4a3565ce53fd685/tests/perf/vec/perf_vector_sort.cc#L20 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 6y ago
  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.
  - leni536 6y ago
    If you pass a function name then the corresponding type template parameter deduces to a function pointer type. Then this function pointer is passed all the way down where the comparison happens, and by that point it's unlikely to be inlined. edit: In this talk this exact scenario is analysed in depth: https://youtu.be/8nyq8SNUTSc?t=435 https://youtu.be/8nyq8SNUTSc?t=435
    - ludocode 6y ago
      It appears you are technically correct. TIL! 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.
trott 6y ago
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/n2271.html http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2007/n227...
- qalmakka 6y ago
  Isn't this somewhat mitigated by the introduction of std::optional<> in C++17? By using it optional<T> instead of T, you can allocate storage while deferring initialization to a latter time (using emplace() or operator=, if T is either moveable or copiable).
  - sgerenser 6y ago
    Perhaps somewhat, but it adds an extra layer of (often) unnecessary complexity. This is especially the case which comes up often where you’re interacting with external libraries or even your own internal, older libraries. For example, if you have a vector, and want to pass its contents to a C API that takes a pointer and length. If it’s a vector of raw values/structs, no problem. If it’s a vector of std::optional<Foo> now you’re stuck unless you go through and recopy the whole thing. 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.
  - gpderetta 6y ago
    you still need to initialize the optional itself. 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.
optymizer 6y ago
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 6y ago
  > 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 6y ago
  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.
  - optymizer 6y ago
    I understand your view and I don't think it's wrong. I have a different set of values for code, and I do like to hang out with people who think like you for periodic reality checks.
ausjke 6y ago
Looks awesome to me. Will use it in future projects. Thanks for the great work.
teabee89 6y ago
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/49b90312f9473057fd2ed77941f8a926429d44be/ctl/vec.h#L269 https://github.com/glouw/ctl/blob/49b90312f9473057fd2ed77941...
- glouwbug 6y ago
  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.
Alupis 6y ago
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 6y ago
  > 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_pattern 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.
  - Alupis 6y ago
    Interesting, I've never heard of CRTP and will need to read up on it. 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...
backpropaganda 6y ago
How would I include the definitions without the implementations?
rurban 6y ago
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 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.

C Template Library

266 points by glouwbug 6y ago

SurfingInVR 6y ago

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

glouwbug 6y ago
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
- souprock 6y ago
  You're missing out on _Generic, _Static_assert, and restrict. https://devblogs.microsoft.com/cppblog/c11-and-c17-standard-support-arriving-in-msvc/ https://devblogs.microsoft.com/cppblog/c11-and-c17-standard-...
- smlckz 6y ago
  You do not need variadic macros! #define foreach(container, variable, iterator) \ for (JOIN(container, it) iterator = JOIN(JOIN(container, it), each) (variable); \ !iterator.done; iterator.step(&iterator)) Is this less nice? I personally do not like dangling )'s [I did not have to write DOS batch scripts :D]
  - glouwbug 6y ago
    Amazing, I can drop the variadic macro. EDIT: Done, and thank you so much - it's so much cleaner this way
    - smlckz 6y ago
      You're welcome. And you might like to see ''sys/queue.h'': https://github.com/openbsd/src/blob/master/sys/sys/queue.h https://github.com/openbsd/src/blob/master/sys/sys/queue.h

glouwbug 6y ago

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 https://github.com/glouw/ctl/wiki

baybal2 6y ago
What do you think about Glib?
ku-man 6y ago
Great work! And thank you for making it available for everyone. Did you also run tests against other libraries such as glib?
nitrogen 6y ago
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 https://github.com/nitrogenlogic/nlutils).
ummonk 6y ago
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 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).
- 6y ago

tu7001 6y ago

Be nice to see a hash map here.

glouwbug 6y ago
Due to popular demand, I will implement unordered_set after the holidays, once the new year is in full swing.
- a-dub 6y ago
  hooray for hashes!
- MrBuddyCasino 6y ago
  In the Java stdlib, Set is implemented on top of HashMap. I don't see how the opposite is possible?
  - glouwbug 6y ago
    Sets (and maps) are implemented as red black trees in the STL. The STL unordered_set (and unordered_map) is what I believe Java would call a HashMap, unless I am mistaken (I am not a Java guru).
    - masklinn 6y ago
      I don't know that the STL requires rbtrees for map and set, but you're correct that `std::unordered_map` is the STL's hashmap. The Java version of std::map would be java.util.TreeMap (and std::set => java.util.TreeSet).
      - tom_mellior 6y ago
        The STL's complexity requirements pretty much dictate a balanced binary search tree as the underlying representation for map and set. The choice then is essentially between red-black trees and AVL trees.
  - 6y ago

deleted 6y ago

[deleted]

notorandit 6y ago

Long live C!

eqvinox 6y ago

Shameless plug: http://docs.frrouting.org/projects/dev-guide/en/latest/lists.html http://docs.frrouting.org/projects/dev-guide/en/latest/lists... https://github.com/FRRouting/frr/blob/master/lib/typesafe.h 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 6y ago
Might as well plug mine too: https://github.com/ludocode/pottery 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.
- eesmith 6y ago
  FWIW, for sorting in a template-like C package I use https://github.com/swenson/sort/ https://github.com/swenson/sort/ .
  - ludocode 6y ago
    That library is included in Pottery's benchmarks! :) It's another of the very few C libraries that use the #include template style. 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.
    - 6y ago

daitangio 6y ago

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 6y ago
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); }
- eqvinox 6y ago
  Wait ... "imagine" - you can't currently do more than one? That's kind of the essential point with templates. (I scrolled through it and assumed you'd just do "#define lst list_charp"?)
  - gpderetta 6y ago
    it seems that it "instantiates" two list types: lst_charp and lst_point and uses both of them. What's the issue?
    - deleted 6y ago
      [deleted]
  - wffurr 6y ago
    “Imagine” as in that code is written in an HN comment, not a C source file, and probably hasn’t been checked with a compiler yet. Why don’t you copy and paste it into a test, try it out, and report back?

blargmaster42_8 6y ago

God the macro bs..and your people have tha audacity to complain about C++....

okaleniuk 6y ago

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

deleted 6y ago

[deleted]

leni536 6y ago

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/09f5e0a89d3fc621aff94290c4a3565ce53fd685/tests/perf/vec/perf_vector_sort.cc#L20 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 6y ago
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.
- leni536 6y ago
  If you pass a function name then the corresponding type template parameter deduces to a function pointer type. Then this function pointer is passed all the way down where the comparison happens, and by that point it's unlikely to be inlined. edit: In this talk this exact scenario is analysed in depth: https://youtu.be/8nyq8SNUTSc?t=435 https://youtu.be/8nyq8SNUTSc?t=435
  - ludocode 6y ago
    It appears you are technically correct. TIL! 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.

trott 6y ago

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/n2271.html http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2007/n227...

qalmakka 6y ago
Isn't this somewhat mitigated by the introduction of std::optional<> in C++17? By using it optional<T> instead of T, you can allocate storage while deferring initialization to a latter time (using emplace() or operator=, if T is either moveable or copiable).
- sgerenser 6y ago
  Perhaps somewhat, but it adds an extra layer of (often) unnecessary complexity. This is especially the case which comes up often where you’re interacting with external libraries or even your own internal, older libraries. For example, if you have a vector, and want to pass its contents to a C API that takes a pointer and length. If it’s a vector of raw values/structs, no problem. If it’s a vector of std::optional<Foo> now you’re stuck unless you go through and recopy the whole thing. 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.
- gpderetta 6y ago
  you still need to initialize the optional itself. 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.

optymizer 6y ago

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 6y ago
> 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 6y ago
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.
- optymizer 6y ago
  I understand your view and I don't think it's wrong. I have a different set of values for code, and I do like to hang out with people who think like you for periodic reality checks.

ausjke 6y ago

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

teabee89 6y ago

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/49b90312f9473057fd2ed77941f8a926429d44be/ctl/vec.h#L269 https://github.com/glouw/ctl/blob/49b90312f9473057fd2ed77941...

glouwbug 6y ago
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.

Alupis 6y ago

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 6y ago
> 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_pattern 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.
- Alupis 6y ago
  Interesting, I've never heard of CRTP and will need to read up on it. 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...

backpropaganda 6y ago

How would I include the definitions without the implementations?

rurban 6y ago

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 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.