search

martinus / robin-hood-hashing

Fast & memory efficient hashtable based on robin hood hashing for C++11/14/17/20
https://gitter.im/martinus/robin-hood-hashing
MIT License
1.5k stars 143 forks source link

Solve diamond problem when hash and equality objects are identical #44

Closed jthemphill closed 4 years ago

jthemphill commented 4 years ago

Solves #43 . To the best of my knowledge, inheriting a class in C++ is really just syntactic sugar for owning a member variable of that class's type. Note that the base classes used to be public, so anyone who invoked call operators on the map itself might have their code break.

martinus commented 4 years ago

Thanks for your work on this! If at all possible I prefer not to introduce any members. I explicitly inherit from hash and equals to avoid creating any members. That way they sizeof(map) does not increase. Also note that the order of members that you use leads to padding: https://travis-ci.com/martinus/robin-hood-hashing/jobs/222671768#L476

martinus commented 4 years ago

After some googling it seems there is a easy workaround possible to prevent the diamond problem. I've added an example here: https://github.com/martinus/robin-hood-hashing/blob/master/src/test/unit/unit_diamond.cpp

jthemphill commented 4 years ago

Ah okay, apparently this is called the Empty Base Optimization. Tears...