c++ unordered_map使用自定义类类型作为键

小开

为了能够将std::unordered_map(或其他无序关联容器之一)与用户定义的键类型一起使用，你需要定义两件事:

一个哈希函数;this必须是一个重写operator()并计算给定key类型对象的哈希值的类。一种特别直接的方法是为你的键类型专门化std::hash模板。

相等比较函数;这是必需的，因为哈希不能依赖于哈希函数总是为每个不同的键提供唯一的哈希值这一事实(即，它需要能够处理冲突)，因此它需要一种方法来比较两个给定的键以获得精确匹配。你可以将其实现为覆盖operator()的类，也可以实现为std::equal的专门化，或者–最简单的–通过为你的键类型重载operator==()(就像你已经做的那样)。

使用哈希函数的困难在于，如果您的键类型由多个成员组成，您通常会让哈希函数计算单个成员的哈希值，然后以某种方式将它们组合成整个对象的一个哈希值。为了获得良好的性能(例如，减少冲突)，您应该仔细考虑如何组合各个哈希值，以确保您避免太频繁地为不同对象获得相同的输出。

哈希函数的一个相当好的起点是使用位移位和按位XOR来组合各个哈希值。例如，假设键类型是这样的:

struct Key
{
std::string first;
std::string second;
int         third;


bool operator==(const Key &other) const
{ return (first == other.first
&& second == other.second
&& third == other.third);
}
};

下面是一个简单的哈希函数(改编自用户定义哈希函数的Cppreference示例中使用的哈希函数):

namespace std {


template <>
struct hash<Key>
{
std::size_t operator()(const Key& k) const
{
using std::size_t;
using std::hash;
using std::string;


// Compute individual hash values for first,
// second and third and combine them using XOR
// and bit shifting:


return ((hash<string>()(k.first)
^ (hash<string>()(k.second) << 1)) >> 1)
^ (hash<int>()(k.third) << 1);
}
};


}

有了这些，你可以为键类型实例化一个std::unordered_map:

int main()
{
std::unordered_map<Key,std::string> m6 = {
{ {"John", "Doe", 12}, "example"},
{ {"Mary", "Sue", 21}, "another"}
};
}

它将自动使用上面定义的std::hash<Key>进行哈希值计算，并使用定义为Key的成员函数的operator==进行相等性检查。

如果你不想在std命名空间内专门化模板(尽管在这种情况下完全合法)，你可以将哈希函数定义为一个单独的类，并将其添加到映射的模板参数列表中:

struct KeyHasher
{
std::size_t operator()(const Key& k) const
{
using std::size_t;
using std::hash;
using std::string;


return ((hash<string>()(k.first)
^ (hash<string>()(k.second) << 1)) >> 1)
^ (hash<int>()(k.third) << 1);
}
};


int main()
{
std::unordered_map<Key,std::string,KeyHasher> m6 = {
{ {"John", "Doe", 12}, "example"},
{ {"Mary", "Sue", 21}, "another"}
};
}

如何定义一个更好的哈希函数?如上所述，定义一个好的哈希函数对于避免冲突和获得良好的性能很重要。对于一个真正的好模型，你需要考虑所有字段的可能值的分布，并定义一个散列函数，将该分布投射到一个尽可能宽且均匀分布的可能结果空间。

这可能很难;上面的异或/位移位方法可能是一个不错的开始。为了更好地开始，你可以使用Boost库中的hash_value和hash_combine函数模板。前者的作用类似于标准类型的std::hash(最近还包括元组和其他有用的标准类型);后者帮助您将单个哈希值合并为一个哈希值。下面是使用Boost辅助函数的哈希函数的重写:

#include <boost/functional/hash.hpp>


struct KeyHasher
{
std::size_t operator()(const Key& k) const
{
using boost::hash_value;
using boost::hash_combine;


// Start with a hash value of 0    .
std::size_t seed = 0;


// Modify 'seed' by XORing and bit-shifting in
// one member of 'Key' after the other:
hash_combine(seed,hash_value(k.first));
hash_combine(seed,hash_value(k.second));
hash_combine(seed,hash_value(k.third));


// Return the result.
return seed;
}
};

下面是一个没有使用boost的重写，但使用了很好的组合哈希的方法:

namespace std
{
template <>
struct hash<Key>
{
size_t operator()( const Key& k ) const
{
// Compute individual hash values for first, second and third
// http://stackoverflow.com/a/1646913/126995
size_t res = 17;
res = res * 31 + hash<string>()( k.first );
res = res * 31 + hash<string>()( k.second );
res = res * 31 + hash<int>()( k.third );
return res;
}
};
}

小开

我认为，jogojapan给出了一个非常好的详尽的回答。在阅读我的文章之前，你绝对应该看看它。但是，我想补充以下几点:

可以为unordered_map单独定义比较函数，而不是使用相等比较操作符(operator==)。这可能是有帮助的，例如，如果你想使用后者来比较两个Node对象的所有成员，但只有一些特定的成员作为unordered_map的键。
你也可以使用lambda表达式来代替定义哈希和比较函数。

总而言之，对于你的Node类，代码可以这样写:

using h = std::hash<int>;
auto hash = [](const Node& n){return ((17 * 31 + h()(n.a)) * 31 + h()(n.b)) * 31 + h()(n.c);};
auto equal = [](const Node& l, const Node& r){return l.a == r.a && l.b == r.b && l.c == r.c;};
std::unordered_map<Node, int, decltype(hash), decltype(equal)> m(8, hash, equal);

注:

我只是在jogojapan的答案的末尾重用了哈希方法，但你可以找到一个更通用的解决方案在这里的想法(如果你不想使用Boost)。
我的代码可能有点太小了。要获得可读性稍强的版本，请参见这个代码在Ideone上。

小开

对于枚举类型，我认为这是一种合适的方式，与类之间的区别是如何计算哈希值。

template <typename T>
struct EnumTypeHash {
std::size_t operator()(const T& type) const {
return static_cast<std::size_t>(type);
}
};


enum MyEnum {};
class MyValue {};


std::unordered_map<MyEnum, MyValue, EnumTypeHash<MyEnum>> map_;

小开

使用自定义类作为unordered_map(稀疏矩阵的基本实现)的键的最基本的可能复制/粘贴完整可运行的示例:

// UnorderedMapObjectAsKey.cpp


#include <iostream>
#include <vector>
#include <unordered_map>


struct Pos
{
int row;
int col;


Pos() { }
Pos(int row, int col)
{
this->row = row;
this->col = col;
}


bool operator==(const Pos& otherPos) const
{
if (this->row == otherPos.row && this->col == otherPos.col) return true;
else return false;
}


struct HashFunction
{
size_t operator()(const Pos& pos) const
{
size_t rowHash = std::hash<int>()(pos.row);
size_t colHash = std::hash<int>()(pos.col) << 1;
return rowHash ^ colHash;
}
};
};


int main(void)
{
std::unordered_map<Pos, int, Pos::HashFunction> umap;


// at row 1, col 2, set value to 5
umap[Pos(1, 2)] = 5;


// at row 3, col 4, set value to 10
umap[Pos(3, 4)] = 10;


// print the umap
std::cout << "\n";
for (auto& element : umap)
{
std::cout << "( " << element.first.row << ", " << element.first.col << " ) = " << element.second << "\n";
}
std::cout << "\n";


return 0;
}

小开

查看下面的链接https://www.geeksforgeeks.org/how-to-create-an-unordered_map-of-user-defined-class-in-cpp/了解更多细节。

自定义类必须实现==运算符
必须为类创建一个哈希函数(对于int等基本类型和string等类型，哈希函数是预定义的)

小开

STL不为pair提供hash函数。您需要自己实现它，并指定为模板参数或将其放入命名空间std中，从那里将自动获取它。遵循https://github.com/HowardHinnant/hash_append/blob/master/n3876.h对于实现结构的自定义哈希函数非常有用。更多的细节在这个问题的其他答案中有很好的解释，所以我不会重复。在Boost中也有类似的东西(hash_combine)。