STL unordered map 自定义键值类型的使用(C++)

首先给大家推荐一下我老师大神的人工智能教学网站。教学不仅零基础,通俗易懂,而且非常风趣幽默,还时不时有内涵黄段子!点这里可以跳转到网站

    当试图使用自定义类型作为 unordered_map 的键值时,则必须为自定义类型定义 Hash 函数与相等的判断条件。我们先定义自定义类型作键值,代码如下:

struct KEY{	int first;	int second;	int third; 	KEY(int f, int s, int t) : first(f), second(s), third(t){}};

    1. Hash 函数

    必须为 override 了 operator() 的一个类,一般自定义类型可能包含几种内置类型,我们可以分别计算出内置类型的 Hash Value 然后对它们进行 Combine 得到一个哈希值,一般直接采用移位加异或(XOR)便可得到还不错的哈希值(碰撞不会太频繁),如下:

struct HashFunc{	std::size_t operator()(const KEY &key) const 	{		using std::size_t;		using std::hash; 		return ((hash<int>()(key.first)			^ (hash<int>()(key.second) << 1)) >> 1)			^ (hash<int>()(key.third) << 1);	}};

    另外一种方法是直接实例化模板,这样的话使用 unordered_map 时便不用再指定 Hash 函数,但要求必须为 KEY 重载 operator ==,实例化模板如下:

namespace std {	template <>	struct hash<KEY>	{		std::size_t operator()(const KEY &key) const		{			using std::size_t;			using std::hash; 			// Compute individual hash values for first,			// second and third and combine them using XOR			// and bit shifting: 			return ((hash<int>()(key.first)				^ (hash<int>()(key.second) << 1)) >> 1)				^ (hash<int>()(key.third) << 1);		}	};}

    2. 相等函数

    哈希需要处理碰撞,意味着必须得知道两个自定义类型对象是否相等,所以必须得提供比较相等的方法,可以 overload operator ==,可以用 std::equal,也可以实现一个 override operator () 的类,这里我们采用后者(这也意味着 Hash 函数不能使用实例化模板的方法,只能定义一个重载了 operator() 的类),代码如下:

struct EqualKey{	bool operator () (const KEY &lhs, const KEY &rhs) const	{		return lhs.first  == rhs.first			&& lhs.second == rhs.second			&& lhs.third  == rhs.third;	}};

    3. 应用实例

    下面为一个具体应用的例子

int main(){	unordered_map<KEY, string, HashFunc, EqualKey> hashmap =	{		{ { 01, 02, 03 }, "one" },		{ { 11, 12, 13 }, "two" },		{ { 21, 22, 23 }, "three" },	}; 	KEY key(11, 12, 13); 	auto it = hashmap.find(key);	 	if (it != hashmap.end()) 	{ 		cout << it->second << endl; 	} 	return 0;}

点这里可以跳转到人工智能网站

发表评论