Sign up for the KDAB Newsletter
Stay on top of the latest news, publications, events and more.
Go to Sign-up
Giuseppe D’Angelo
23 March 2021
In the previous blog post about qHash,
we explained:
qHash
for your own datatypes,In this post, we'll continue our discussion regarding hashing functions, tackling a specific problem, namely, how to use a Qt datatype as a key of a Standard Library unordered associative container.
The Standard Library unordered associative containers (std::unordered_map
, std::unordered_set
, and so on), as well as other third party implementations (like the excellent robin-map), require, by default, a specialization of std::hash
to be available for the key type we want to use. For instance:
// OK, uses std::hash<int>, which is provided by the Standard Library
std::unordered_set<int> int_set;
// OK, uses std::hash<QString>, which is provided by Qt
std::unordered_set<QString> string_set;
// ERROR: std::hash<QDateTime> does not exist
std::unordered_set<QDateTime> date_set;
How do we solve the last case (or any other similar case)? Note that QDateTime has an existing qHash
overload, so it can be hashed efficiently; it's just missing support for std::hash
.
The problem we face here is that adding a std::hash specialization for a type T is a prerogative of T's author. In other words, we are not supposed to add a specialization for a type we don't control. This includes Qt's own datatypes, which, in huge majority, do not come with std::hash
support (in fact, only a handful of classes currently have with such support).
We have two solutions to this problem:
std::hash
for it. We can implement the hashing simply in terms of the existing qHash
function for the type. The problem with this solution is that it might be slightly annoying to have to deal such a wrapper the entire time we interact with the associative container.std::hash
, without the need of creating extra data types.The second solution exploits the fact that the Standard Library associative containers specify the hashing function as a customization point. You can always decide not to use std::hash,
but something else, by specifying the hasher type to use as a template parameter:
struct QDateTimeHasher {
size_t operator()(const QDateTime &dt) const noexcept {
// ... calculate the hash ...
}
};
// Uses QDateTimeHasher as the hashing function for this map
std::unordered_map<QDateTime, Event, QDateTimeHasher> date_to_event_map;
The calculation of the hash can be offloaded to the existing qHash(QDateTime)
overload, so we don't actually have to come up with its implementation.
Thinking about it, the very same approach we just used for QDateTime
can, in fact, be generalized to any Qt class that offers a qHash
overload.
struct QDateTimeHasher {
size_t operator()(const QDateTime &dt) const noexcept {
return qHash(dt);
}
};
struct QPointHasher {
size_t operator()(const QPoint &dt) const noexcept {
return qHash(dt);
}
};
// ... repeat for any other Qt datatype ...
Do you know what this means? It means say hello to our little friend -- KDToolBox, KDAB's collection of miscellaneous useful C++ classes and stuff.
The QtHasher helper class we've added to KDToolBox can be used as an off-the-shelf solution. It's a hasher class that simply uses qHash
, just as shown above, thus solving the problem centrally:
std::unordered_map<QDateTime,
Event,
KDToolBox::QtHasher<QDateTime>> map;
KDToolBox is freely available here.
Thanks for reading, and I'll see you next time.
About KDAB
The KDAB Group is a globally recognized provider for software consulting, development and training, specializing in embedded devices and complex cross-platform desktop applications. In addition to being leading experts in Qt, C++ and 3D technologies for over two decades, KDAB provides deep expertise across the stack, including Linux, Rust and modern UI frameworks. With 100+ employees from 20 countries and offices in Sweden, Germany, USA, France and UK, we serve clients around the world.
Stay on top of the latest news, publications, events and more.
Go to Sign-up
Learn Modern C++
Our hands-on Modern C++ training courses are designed to quickly familiarize newcomers with the language. They also update professional C++ developers on the latest changes in the language and standard library introduced in recent C++ editions.
Learn more