4 ms·

You can look at the source in his github repository: https://github.com/skarupke/flat_hash_map https://github.com/skarupke/flat_hash_map

dividuum 8y ago
That's not the same as having a high level description of the concepts used. For details I can still dive into the details later.
titzer 8y ago
I looked through the code and o_O there is a lot of C++ boilerplate. The core part of it is not really documented well, and there is this mysterious jump bits array...if I had more time, I could figure out it. But that's the point of a writeup, explaining things with a diagram, etc.
- Tomis02 8y ago
  To be honest, when it comes to C++ boilerplate, I've seen much, much worse. At a first glance the code looks somewhat clean.
- jcelerier 8y ago
  > I looked through the code and o_O there is a lot of C++ boilerplate. This boilerplate allows me to choose between std::unordered_map and flat_hash_map in my whole code just by toggling a compile time switch in my code. It ensures that the data structures has the same API than all other C++ containers.
  - titzer 8y ago
    I understand what it is for. YMMV but for me C++ is pretty much a constant mental stack overflow when reading the guts like this. It seems like C++ libraries are getting more and more configurable in a way that hurts readability and understandability and library designers don't seem to recognize there is a fundamental tradeoff here.
    - jcelerier 8y ago
      > It seems like C++ libraries are getting more and more configurable in a way that hurts readability and understandability and library designers don't seem to recognize there is a fundamental tradeoff here. well, I mean... if it was not configurable, it would not really be useful, except for toy examples, and for those the default std::unordered_map is more than sufficient. To be useful, a hash table implementation at least needs to allow to configure the hash function and the comparison operator.
    - kwillets 8y ago
      I actually have separate implementations of an algorithm with and without templates; the template one is for benchmarking with different combinations of options; the non-template one is for readability, and it's only about 60 lines.

dividuum 8y ago

That's not the same as having a high level description of the concepts used. For details I can still dive into the details later.

titzer 8y ago

I looked through the code and o_O there is a lot of C++ boilerplate. The core part of it is not really documented well, and there is this mysterious jump bits array...if I had more time, I could figure out it. But that's the point of a writeup, explaining things with a diagram, etc.

Tomis02 8y ago
To be honest, when it comes to C++ boilerplate, I've seen much, much worse. At a first glance the code looks somewhat clean.
jcelerier 8y ago
> I looked through the code and o_O there is a lot of C++ boilerplate. This boilerplate allows me to choose between std::unordered_map and flat_hash_map in my whole code just by toggling a compile time switch in my code. It ensures that the data structures has the same API than all other C++ containers.
- titzer 8y ago
  I understand what it is for. YMMV but for me C++ is pretty much a constant mental stack overflow when reading the guts like this. It seems like C++ libraries are getting more and more configurable in a way that hurts readability and understandability and library designers don't seem to recognize there is a fundamental tradeoff here.
  - jcelerier 8y ago
    > It seems like C++ libraries are getting more and more configurable in a way that hurts readability and understandability and library designers don't seem to recognize there is a fundamental tradeoff here. well, I mean... if it was not configurable, it would not really be useful, except for toy examples, and for those the default std::unordered_map is more than sufficient. To be useful, a hash table implementation at least needs to allow to configure the hash function and the comparison operator.
  - kwillets 8y ago
    I actually have separate implementations of an algorithm with and without templates; the template one is for benchmarking with different combinations of options; the non-template one is for readability, and it's only about 60 lines.