Using QString as the key in std::unordered_map

Question

I'm trying to use QString as the key in a std::unordered_map, however I get the error:

error C2280: 'std::hash<_Kty>::hash(const std::hash<_Kty> &)': attempting to reference a deleted function

I can't switch to QHash because the value-type of the map is non-copyable. Is there any way to make this work?

Unblinking

Answer 1

Put the hash implementation in a header, and make sure that you include that header everywhere the map is used.

A trivial implementation that forwards to qHash should be sufficient:

#include <QHash>
#include <QString>
#include <functional>

namespace std {
  template<> struct hash<QString> {
    std::size_t operator()(const QString& s) const noexcept {
      return (size_t) qHash(s);
    }
  };
}

Even though std::size_t is larger than unsigned int on common 64 bit platforms, and thus the hash doesn't change across its full length - this isn't a problem. The standard places no such requirement on an std::hash implementation.

---

Let's not forget, though, that modifying anything in the std namespace is generally undefined behavior and unnecessary.

TL;DR:
You're allowed to specialize certain type and variable templates, and only if the specialization depends on at least one user-defined type. You can't fully specialize for built-in nor C++ library types.

See Extending the namespace std for reference. There, we read:

It is undefined behavior to add declarations or definitions to namespace std or to any namespace nested within std, with a few exceptions noted below.

Mainly, it is allowed to specialize certain types in the std namespace:

It is allowed to add template specializations for any standard library class template to the namespace std only if the declaration depends on at least one program-defined type and the specialization satisfies all requirements for the original template, except where such specializations are prohibited.

Note that what's legal is specializing types, i.e. classes. Functions and member functions? Not ever:

It is undefined behavior to declare a full specialization of any standard library function template, [... or] member function of a standard library class template, [... or] member function template of a standard library class or class template.

Another limited exception is for variable templates:

It is undefined behavior to declare a full or partial specialization of any standard library variable template, except where explicitly allowed.

Emphasis mine in all cases. As always, there are further details that one should get acquainted with.

Arron

Answer 2

The problem is that there is no std::hash<QString>() specialization. It's easy enough to define your own with reasonably good performance based on the dbj2 algorithm:

#include <QString>
#include <unordered_map>

namespace std
{
    template<> struct hash<QString>
    {
        std::size_t operator()(const QString& s) const noexcept
        {
            const QChar* str = s.data();
            std::size_t hash = 5381;

            for (int i = 0; i < s.size(); ++i)
                hash = ((hash << 5) + hash) + ((str->row() << 8) | (str++)->cell());

            return hash;
        }
    };
}

include that in files which use a QString in a std::unordered_map and the error goes away.

Unblinking

You can simplify that to return std::hash<std::string>()(s.toStdString()); – Bui

@RSahu sure could, but it won't be as performant due to the unicode to utf8 conversion and the memory allocation. – Unblinking

Probably even return qHash(s). – Noakes

@NicolasHolthaus, that is true. – Bui

This answer is incorrect, since QString can contain internal \0 characters. – Tapp

@Tapp thanks, didn't realize that. I'll make an edit. – Unblinking

Like said before, it's simpler just to return qHash value. – Tapp

Answer 3

It seems that in newer versions of Qt, std::hash is defined for QString so you can use it with std::unordered_map directly. (It works with Qt 5.14 on my machine.)

Ahmedahmedabad