Are you tired of creating comparators or hashes for your custom class? I have a solution for you.
Sometimes we need to use STL data structures such as map, unordered_map or set using a data type that doesn't have a hash or a comparator. Instead of coding things properly I will show an easy way to achieve the same thing with minimal effort.
The idea is to use pointer casting.
Let's say we want to use pair<int,int> with an unordered_map (notice that there's no pre-made hash for this data type).
The size of pair<int,int> is 8 bytes. Also notice that we have long long: a data type also 8 bytes long.
We can create an unordered_map, and to check our pair we can just do:
typedef std::pair<int,int> pii;
std::unordered_map<long long,int> hashmap;
pii object;
hashmap[*((long long*)&object)] = 24;
We can recast our data type for another data type of the same size, and it will work just fine! But we don't have endless integers to use. Is there an easier way that is able to store any data structure?
Luckily there is!
We can use bitsets, and resize them as we wish. Following our previous example:
typedef std::pair<int,int> pii;
typedef std::bitset<sizeof(pii)*8> bits;
std::unordered_map<bits,int> hashmap;
pii object;
hashmap[*((bits*)&object)] = 24;
Here we create a bitset exactly the size of our class, making us able to use any standard container with our pair<int,int>.
Reason for this blog: I have used this trick for a somewhat long time, but it seems that not many programmers are aware of this method (+ I didn't find anything talking about this technique), so here it is :)
Auto comment: topic has been updated by Deepesson (previous revision, new revision, compare).
Also, I think it's worth mentioning that with a couple macros we can make our code really small:
Can use
for a bit more C++ flavor, instead of C style casting, because technically C style cast can do a bunch of unexpected things.
Also if you are going to use this trick, be aware that you are comparing the bit patterns of the objects, which might not necessarily be the same for equivalent objects. For example, you can't just compare the bit patterns of 2 std::string object to see if they are the same, you have to compare the data.
It might also be possible to create a template wrapper class to automatically do this. It might also be possible to just implement a bunch of structured bindings to compare objects field by field automatically, but it might have high overhead.
I have come to prove myself with the last part. The following code lexicographically compare any 2 objects of the same class. (Need C++20).
The most significant part of the implementation is the
construct_arity
template, which I unashamedly copied from somewhere. This count the number of fields inside a class, by binary searching the amount of field and check if we can construct the object from that many field. This is all done at compile time, but there's some problem:After that, you can see the
compare
function which return-1, 0, 1
when thelhs
is less, greater than, or equal to therhs
.Currently the code need to manually handle the various arities. I have handled up to 5.
It is probably possible (and maybe better) to just implement something similar to
std::get
(magic_get might be one such thing), then we don't have to handle everything manually. In the implementation, I have opted to copy theFOR_EACH
macro.It's easy to see that this idea can also be expanded to a hashing function (just call
std::hash
in the base case, and callstd::hash
on the fields' resulting hashes otherwise).Overall, this was a nice exercise that wasted plenty of time for both me and those of you who read until now.
reinterpret_cast
is not enough because it breaks strict aliasing rule. It's better to usebit_cast
after c++20.That's true. I have not updated my things to the newest stuff.
Nice