Using Qt Datatypes in Standard Library Unordered Containers

23.03.2021 Giuseppe D'Angelo No comments

In the previous blog post about qHash, we explained:

• how to declare an overload of qHash for your own datatypes,
• how to hash Qt datatypes for which Qt does not provide a qHash overload, and
• why you can’t use a type from the Standard Library (or just another library) as a key in QHash (newsflash: this has changed! More on it later).

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:

1. We can use a wrapper class (or a subclass) of the Qt datatype. Such a class is going to be under our control, and, therefore, we are allowed to specialize 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.
2. We can use a different hashing function than 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.

I sense a pattern here…

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.