7 ms·

Writing your own C++ standard library part 2

83 points by signa11 1y ago

jandrewrogers 1y ago
I’ve said it many times: a pure C++20 standard library imagined from first principles with total disregard for legacy code would do amazing things for the reputation and value of C++ as a language. It could be so much better than it is. Yes, I understand, compatibility. At some point, clean new code bases should not be burdened with that albatross.
- thenewwazoo 1y ago
  Isn't that just abseil? https://abseil.io https://abseil.io
  - jandrewrogers 1y ago
    Not even close, and I am a fan of abseil. The design of abseil has legacy constraints that don’t need to apply to a C++20 clean room implementation. I have better re-implementations of abseil components in my own “standard” library simply because I didn’t have those constraints. There are many good libraries out there, or fragments of libraries, but I’ve never found one that really scratches this itch.
    - hoten 1y ago
      Could you give a couple examples?
      - krapht 1y ago
        Of libraries that are better than the STL? Or data structures that the STL is missing? Without getting into the weeds of esoteric data structures and algorithms I think there's a few holes that aren't addressed: https://github.com/martinus/unordered_dense https://github.com/martinus/unordered_dense provides better replacements for unordered_map/set. The STL is missing B-trees and B-heaps, as well as d-heaps. STL is also missing a radix sort, which is even more sorely missed now that we have std::executor::par_unseq to play with.
        maattdd 1y ago
        Examples of better design than abseil in a pure C++20 implementation
- jll29 1y ago
  Compatibility is not a reason for not attempting to realize your proposal. (One just needs a difference namespace from "std" e.g. "lib".)
- monkeyelite 1y ago
  The problem with C++ is not a bad standard library. It’s probably one of the best algorithms and containers libraries in any language.
  - 112233 1y ago
    What are you comparing it to? Because wow.
    - monkeyelite 1y ago
      Same question for you.
      - 112233 1y ago
        Every time I have to work with text in C++ using stl feels like pulling teeth. It has gotten better over years, but even php gives one stdlib envy. The idea to base everything on iterators instead of ranges, blowing up the code (and amount of errors) — it would have made sense for pure algorithms, but stl insists on having ownership of object placed in the containers. No sane way to work with binary data. Inconsistent allocation and exception ideology through the years. Mysteriously missing functionality. What little ruby, python, php I have written — nothing has felt as clunky as STL. E.g. vector has no "sort" member function. What great benefit not adding it for convenience has brought?
  - platinumrad 1y ago
    <algorithm> is a very good header, but most of the containers are substandard at best. `std::unordered_map` is required to be node-based, `std::map` can't be a B-tree, MSVC's implementation of `std::deque` is infamously a glorified `std::list`, and so on. Pretty much everything else (e.g. iostreams) is horrible.
    - TuxSH 1y ago
      Don't forget <tuple> not mandated to be trivial when it can be (and in fact never being trivial with GCC's stdlib), std::print performance issues (see P3107R5, P3235R3), etc. Heck, even std::atomic was designed with only x64 in mind (it clearly shows), and is unusable outside it. One is incentivized to write their own "atomic" class until P3330R0 is approved for RMW-centric platforms ISAs like Aarch32 and Aarch64. And of course, Rust already has "fetch_update"...
- prydt 1y ago
  Have you seen libkj [1]? I've used it and really enjoy working with it. It has a rust-like owned pointer and the whole library uses these smart pointers. It has proper container classes based on B-trees and its also got an async runtime. [1] https://github.com/capnproto/capnproto/blob/v2/kjdoc/index.md https://github.com/capnproto/capnproto/blob/v2/kjdoc/index.m...
- jeroenhd 1y ago
  I like SerenityOS' "standard library". It has some Rust-like features (like ErrorOr, which is a lot like Result) but also some C++ usability enhancement that make use of modern C++ features rather than trying to force a C++-shaped peg into a POSIX-shaped hole. The only exception I know of is the pledge() implementation (which uses a space separated string rather than something like an array of enum values), but having pledge() at all is a pretty major improvement. SerenityOS' original "make no use of external libraries" approach made one of the more complete re-imaginings of the C++ application landscape I've seen. It really changed my perspective on what C++ could be.
  - tyrellj 1y ago
    I was curious, and a bit distractible this morning, so I took a look at their git repo. I did some osdev tinkering in college so I find this all interesting. AK seems to be their standard library that you were mentioning, but there's some interesting things going on in their Libraries dir too. https://github.com/SerenityOS/serenity/blob/master/AK/ https://github.com/SerenityOS/serenity/blob/master/AK/ https://github.com/SerenityOS/serenity/blob/master/AK/Result.h https://github.com/SerenityOS/serenity/blob/master/AK/Result... https://github.com/SerenityOS/serenity/tree/master/Userland/Libraries https://github.com/SerenityOS/serenity/tree/master/Userland/...
- kgeist 1y ago
  D already had this, 2 "standard" libraries: https://news.ycombinator.com/item?id=6066174 https://news.ycombinator.com/item?id=6066174 >The reason it caused the division at community is that the ones that you could not use both on the same project, this meant that for a while you had two "D" languages that were separate, libraries made with one did not worked with the other...
- deleted 1y ago
  [deleted]
azhenley 1y ago
> The post got linked by Hackernews and Reddit. As is usual the majority of comments did not talk about the actual content but instead were focused on two tangential things. Too true, and this is too good. Start with part 1 (and the comments) if you haven’t.
- rzzzt 1y ago
  If you want to read the referenced comments, here they are (probably -- I don't have a crystal ball, only access to a search engine): - https://news.ycombinator.com/item?id=43468976 https://news.ycombinator.com/item?id=43468976 - https://www.reddit.com/r/programming/comments/1jjluxe/writing_your_own_c_standard_library_from_scratch/ https://www.reddit.com/r/programming/comments/1jjluxe/writin...
- ryandrake 1y ago
  I wonder what it is about the HN audience or about the HN voting system that seems to always result in this. You see this in so many stories posted here: Out of a 1000 word article, someone nitpicks a single phrase, and 75% of the comments rathole on that discussion rather than talking about the article.
  - account42 1y ago
    It's quite simple. These sites are frequented by humans how have their own interests and sometimes agendas rather than by automatons who only discuss what you personally want them to discuss. Hope that clears it up.
  - steveklabnik 1y ago
    This is: 1. hilarious because it itself is an example of this behavior, we aren't discussing the article, but instead a tangent from a few words from it 2. an instance of Parkinson's Law of Triviality: it's just easier to respond to a comment than to read an entire article. Plus, many people read comments first to try and determine if an article is worth reading. So you end up with engagement in spinoff discussion, especially when the original is harder to read or understand to a general audience.
comex 1y ago
> Sadly there is not a simple way to integrate this to native loop constructs without macros and even then it is a bit ugly. I’ve implemented something like this before, without macros. It’s a little ugly, but not that bad IMO. If you write a native range-based for loop: for (auto foo : obj) { /* do something */ } it essentially desugars to auto it = foo.begin(); auto end = foo.end(); for (; it != end; ++it) { auto foo = *it; /* do something */ } To make it work with a custom type, you need to implement `begin()` and `end()` methods, but the returned objects don’t need to support the full STL iterator protocol; they only need to support the exact sequence of operations from the desugaring. So, for example, `end()` can return a unique `End` type that contains no data and does nothing. `begin()` can return a different type that does all the real work and implements `operator!=(End)`. With that, it’s not too hard to implement a wrapper around a Python-like iterator protocol. The main drawback is that you need to temporarily store each item in the begin object before it’s moved into the iteration variable. This is because you have to already know whether a next item exists at the point of `it != end`, but then the item isn’t actually retrieved until `*it`. The extra move has a slight cost, but the compiler can often optimize it away to nothing. You can also avoid this if the for loop uses a reference type (`for (auto& foo : obj)`).
- 112233 1y ago
  (Since c++17) The technique you so well describe in your comment does not work with the original range for :( Not that it is an issue anymore, but I'd forgive anyone who tried to write code like this when range for was added from not trying anymore, because they remember the original semantics. The page: https://cppreference.com/w/cpp/language/range-for.html https://cppreference.com/w/cpp/language/range-for.html reads like a testimony in a negligence court case.
- tubs 1y ago
  I think you can also define begin/end as non member functions (eg if you don’t own the code for the type).
monkeyelite 1y ago
Python iterators are simple, but also less capable, for example you cannot easily modify a container using them. In C++ this is equivalent to an InputIterator.
- few 1y ago
  I have many years of experience writing C++. I still can't iterate and delete from a map without looking it up (if not allowed to use erase_if).
  - OskarS 1y ago
    Both of these things are very easy to do in modern C++: // erase map.erase(2); // iterate for (auto &[k,v]: map) { // do stuff } godbolt: https://godbolt.org/z/o8f6zhqxq https://godbolt.org/z/o8f6zhqxq
    - maattdd 1y ago
      Obviously you can delete than iterate. He means delete while iterating.
      - incrudible 1y ago
        What is the use case for that? Seems more like a footgun, at least for a generic container interface.
        gpderetta 1y ago
        It happens surprisingly often.
        simonask 1y ago
        Surely you must be kidding? Inserting/removing in a container while iterating through it is one of the all time greatest and most iconic bugs. People do it because they want to do it. In reality, very few real-life containers can support this pattern, which is why this is a headline case for Rust, because it statically prevents this bug. But yes, for removal the correct thing is always to use `std::erase_if` (C++) or `retain()` (Rust). For insertions, the only real solution is to build up a separate collection while iterating and then merging it into the original container when done. Yucky, but won't crash.
tialaramex 1y ago
> proof that the person saying that does not understand the C++ language. This was followed by several "I am a C++ standard library implementer and everyone I know calls it the STL". Things deteriorated from there. It feels natural to assume that the implementers and long time WG21 members must understand the language, but this is not true. C++ spiralled well beyond the capability of a person to actually understand it years ago. Maybe that's unfair, but it's unusual. This is a constructed language, its syntax and semantics matter greatly and yet in practice our grasp of its meaning is more akin to that for say, English, than for Perl or Rust. There are contradictory style guides, people with well meant rules of thumb contradicted by a world of real usage, numerous dialects, not to mention people who strongly believe other users of the language are "doing it wrong" and yet what they're doing works fine.
- pjmlp 1y ago
  This is a recent blog post from DirectX team, https://devblogs.microsoft.com/directx/omm/ https://devblogs.microsoft.com/directx/omm/ Compare the C++ code samples with the Modern C++ usually talked about C++ conferences. This is why I keep saying I only see such high bar code on conference slides, and my hobby projects, those DirectX code samples are much more closer to daily C++ written in big corporations, ironically even those that are C++ compiler vendors with seats at WG21. On the other hand, there are many industries where I don't see Rust taking anything meaningful away from either C or C++, regardless of how much we complain about them, or how much better Rust happens to be over them.
  - jeroenhd 1y ago
    Microsoft's DirectX C++ example code needs to interact with DirectX' C APIs. That will easily lead to "C with classes" C++ when most of the code is interacting with foreign APIs, like these API demos do. I think open-source software like https://github.com/microsoft/WSL https://github.com/microsoft/WSL is probably more representative of what modern C++ companies look like. Plenty of files that just interact with OS C APIs, but no shortage of modern C++ features in use.
    - 1y ago

83 points by signa11 1y ago

I’ve said it many times: a pure C++20 standard library imagined from first principles with total disregard for legacy code would do amazing things for the reputation and value of C++ as a language. It could be so much better than it is. Yes, I understand, compatibility. At some point, clean new code bases should not be burdened with that albatross.

thenewwazoo 1y ago
Isn't that just abseil? https://abseil.io https://abseil.io
- jandrewrogers 1y ago
  Not even close, and I am a fan of abseil. The design of abseil has legacy constraints that don’t need to apply to a C++20 clean room implementation. I have better re-implementations of abseil components in my own “standard” library simply because I didn’t have those constraints. There are many good libraries out there, or fragments of libraries, but I’ve never found one that really scratches this itch.
  - hoten 1y ago
    Could you give a couple examples?
    - krapht 1y ago
      Of libraries that are better than the STL? Or data structures that the STL is missing? Without getting into the weeds of esoteric data structures and algorithms I think there's a few holes that aren't addressed: https://github.com/martinus/unordered_dense https://github.com/martinus/unordered_dense provides better replacements for unordered_map/set. The STL is missing B-trees and B-heaps, as well as d-heaps. STL is also missing a radix sort, which is even more sorely missed now that we have std::executor::par_unseq to play with.
      - maattdd 1y ago
        Examples of better design than abseil in a pure C++20 implementation
jll29 1y ago
Compatibility is not a reason for not attempting to realize your proposal. (One just needs a difference namespace from "std" e.g. "lib".)
monkeyelite 1y ago
The problem with C++ is not a bad standard library. It’s probably one of the best algorithms and containers libraries in any language.
- 112233 1y ago
  What are you comparing it to? Because wow.
  - monkeyelite 1y ago
    Same question for you.
    - 112233 1y ago
      Every time I have to work with text in C++ using stl feels like pulling teeth. It has gotten better over years, but even php gives one stdlib envy. The idea to base everything on iterators instead of ranges, blowing up the code (and amount of errors) — it would have made sense for pure algorithms, but stl insists on having ownership of object placed in the containers. No sane way to work with binary data. Inconsistent allocation and exception ideology through the years. Mysteriously missing functionality. What little ruby, python, php I have written — nothing has felt as clunky as STL. E.g. vector has no "sort" member function. What great benefit not adding it for convenience has brought?
- platinumrad 1y ago
  <algorithm> is a very good header, but most of the containers are substandard at best. `std::unordered_map` is required to be node-based, `std::map` can't be a B-tree, MSVC's implementation of `std::deque` is infamously a glorified `std::list`, and so on. Pretty much everything else (e.g. iostreams) is horrible.
  - TuxSH 1y ago
    Don't forget <tuple> not mandated to be trivial when it can be (and in fact never being trivial with GCC's stdlib), std::print performance issues (see P3107R5, P3235R3), etc. Heck, even std::atomic was designed with only x64 in mind (it clearly shows), and is unusable outside it. One is incentivized to write their own "atomic" class until P3330R0 is approved for RMW-centric platforms ISAs like Aarch32 and Aarch64. And of course, Rust already has "fetch_update"...
prydt 1y ago
Have you seen libkj [1]? I've used it and really enjoy working with it. It has a rust-like owned pointer and the whole library uses these smart pointers. It has proper container classes based on B-trees and its also got an async runtime. [1] https://github.com/capnproto/capnproto/blob/v2/kjdoc/index.md https://github.com/capnproto/capnproto/blob/v2/kjdoc/index.m...
jeroenhd 1y ago
I like SerenityOS' "standard library". It has some Rust-like features (like ErrorOr, which is a lot like Result) but also some C++ usability enhancement that make use of modern C++ features rather than trying to force a C++-shaped peg into a POSIX-shaped hole. The only exception I know of is the pledge() implementation (which uses a space separated string rather than something like an array of enum values), but having pledge() at all is a pretty major improvement. SerenityOS' original "make no use of external libraries" approach made one of the more complete re-imaginings of the C++ application landscape I've seen. It really changed my perspective on what C++ could be.
- tyrellj 1y ago
  I was curious, and a bit distractible this morning, so I took a look at their git repo. I did some osdev tinkering in college so I find this all interesting. AK seems to be their standard library that you were mentioning, but there's some interesting things going on in their Libraries dir too. https://github.com/SerenityOS/serenity/blob/master/AK/ https://github.com/SerenityOS/serenity/blob/master/AK/ https://github.com/SerenityOS/serenity/blob/master/AK/Result.h https://github.com/SerenityOS/serenity/blob/master/AK/Result... https://github.com/SerenityOS/serenity/tree/master/Userland/Libraries https://github.com/SerenityOS/serenity/tree/master/Userland/...
kgeist 1y ago
D already had this, 2 "standard" libraries: https://news.ycombinator.com/item?id=6066174 https://news.ycombinator.com/item?id=6066174 >The reason it caused the division at community is that the ones that you could not use both on the same project, this meant that for a while you had two "D" languages that were separate, libraries made with one did not worked with the other...
deleted 1y ago
[deleted]

azhenley 1y ago

> The post got linked by Hackernews and Reddit. As is usual the majority of comments did not talk about the actual content but instead were focused on two tangential things. Too true, and this is too good. Start with part 1 (and the comments) if you haven’t.

rzzzt 1y ago
If you want to read the referenced comments, here they are (probably -- I don't have a crystal ball, only access to a search engine): - https://news.ycombinator.com/item?id=43468976 https://news.ycombinator.com/item?id=43468976 - https://www.reddit.com/r/programming/comments/1jjluxe/writing_your_own_c_standard_library_from_scratch/ https://www.reddit.com/r/programming/comments/1jjluxe/writin...
ryandrake 1y ago
I wonder what it is about the HN audience or about the HN voting system that seems to always result in this. You see this in so many stories posted here: Out of a 1000 word article, someone nitpicks a single phrase, and 75% of the comments rathole on that discussion rather than talking about the article.
- account42 1y ago
  It's quite simple. These sites are frequented by humans how have their own interests and sometimes agendas rather than by automatons who only discuss what you personally want them to discuss. Hope that clears it up.
- steveklabnik 1y ago
  This is: 1. hilarious because it itself is an example of this behavior, we aren't discussing the article, but instead a tangent from a few words from it 2. an instance of Parkinson's Law of Triviality: it's just easier to respond to a comment than to read an entire article. Plus, many people read comments first to try and determine if an article is worth reading. So you end up with engagement in spinoff discussion, especially when the original is harder to read or understand to a general audience.

comex 1y ago

> Sadly there is not a simple way to integrate this to native loop constructs without macros and even then it is a bit ugly. I’ve implemented something like this before, without macros. It’s a little ugly, but not that bad IMO. If you write a native range-based for loop: for (auto foo : obj) { /* do something */ } it essentially desugars to auto it = foo.begin(); auto end = foo.end(); for (; it != end; ++it) { auto foo = *it; /* do something */ } To make it work with a custom type, you need to implement `begin()` and `end()` methods, but the returned objects don’t need to support the full STL iterator protocol; they only need to support the exact sequence of operations from the desugaring. So, for example, `end()` can return a unique `End` type that contains no data and does nothing. `begin()` can return a different type that does all the real work and implements `operator!=(End)`. With that, it’s not too hard to implement a wrapper around a Python-like iterator protocol. The main drawback is that you need to temporarily store each item in the begin object before it’s moved into the iteration variable. This is because you have to already know whether a next item exists at the point of `it != end`, but then the item isn’t actually retrieved until `*it`. The extra move has a slight cost, but the compiler can often optimize it away to nothing. You can also avoid this if the for loop uses a reference type (`for (auto& foo : obj)`).

112233 1y ago
(Since c++17) The technique you so well describe in your comment does not work with the original range for :( Not that it is an issue anymore, but I'd forgive anyone who tried to write code like this when range for was added from not trying anymore, because they remember the original semantics. The page: https://cppreference.com/w/cpp/language/range-for.html https://cppreference.com/w/cpp/language/range-for.html reads like a testimony in a negligence court case.
tubs 1y ago
I think you can also define begin/end as non member functions (eg if you don’t own the code for the type).

monkeyelite 1y ago

Python iterators are simple, but also less capable, for example you cannot easily modify a container using them. In C++ this is equivalent to an InputIterator.

few 1y ago
I have many years of experience writing C++. I still can't iterate and delete from a map without looking it up (if not allowed to use erase_if).
- OskarS 1y ago
  Both of these things are very easy to do in modern C++: // erase map.erase(2); // iterate for (auto &[k,v]: map) { // do stuff } godbolt: https://godbolt.org/z/o8f6zhqxq https://godbolt.org/z/o8f6zhqxq
  - maattdd 1y ago
    Obviously you can delete than iterate. He means delete while iterating.
    - incrudible 1y ago
      What is the use case for that? Seems more like a footgun, at least for a generic container interface.
      - gpderetta 1y ago
        It happens surprisingly often.
      - simonask 1y ago
        Surely you must be kidding? Inserting/removing in a container while iterating through it is one of the all time greatest and most iconic bugs. People do it because they want to do it. In reality, very few real-life containers can support this pattern, which is why this is a headline case for Rust, because it statically prevents this bug. But yes, for removal the correct thing is always to use `std::erase_if` (C++) or `retain()` (Rust). For insertions, the only real solution is to build up a separate collection while iterating and then merging it into the original container when done. Yucky, but won't crash.

tialaramex 1y ago

> proof that the person saying that does not understand the C++ language. This was followed by several "I am a C++ standard library implementer and everyone I know calls it the STL". Things deteriorated from there. It feels natural to assume that the implementers and long time WG21 members must understand the language, but this is not true. C++ spiralled well beyond the capability of a person to actually understand it years ago. Maybe that's unfair, but it's unusual. This is a constructed language, its syntax and semantics matter greatly and yet in practice our grasp of its meaning is more akin to that for say, English, than for Perl or Rust. There are contradictory style guides, people with well meant rules of thumb contradicted by a world of real usage, numerous dialects, not to mention people who strongly believe other users of the language are "doing it wrong" and yet what they're doing works fine.

pjmlp 1y ago
This is a recent blog post from DirectX team, https://devblogs.microsoft.com/directx/omm/ https://devblogs.microsoft.com/directx/omm/ Compare the C++ code samples with the Modern C++ usually talked about C++ conferences. This is why I keep saying I only see such high bar code on conference slides, and my hobby projects, those DirectX code samples are much more closer to daily C++ written in big corporations, ironically even those that are C++ compiler vendors with seats at WG21. On the other hand, there are many industries where I don't see Rust taking anything meaningful away from either C or C++, regardless of how much we complain about them, or how much better Rust happens to be over them.
- jeroenhd 1y ago
  Microsoft's DirectX C++ example code needs to interact with DirectX' C APIs. That will easily lead to "C with classes" C++ when most of the code is interacting with foreign APIs, like these API demos do. I think open-source software like https://github.com/microsoft/WSL https://github.com/microsoft/WSL is probably more representative of what modern C++ companies look like. Plenty of files that just interact with OS C APIs, but no shortage of modern C++ features in use.
  - 1y ago