C++ unordered_map自定义key

前言

今天刷Leetcode的时候,使用了pair<>作为unordered_map的key,编译时报错。

解决

如果没有特殊的需要,可以使用map来代替unordered_map,这样可以通过编译

原因

map是有序的,底层使用的红黑树,map需要对key进行相互比较,从而确定具体插入的位置,所以map的key值需要支持比较函数。而pair重载了相对应的比较操作符,所以使用map没有问题

相反,unordered_map是无序的,是基于哈希表的数据结构,unordered_map需要对key进行hash函数,利用hash出的唯一值确定插入对象的位置,所以unordered_map的key值需要支持hash函数,而pair没有默认的hash函数,所以会编译出错

当然,我们也可以自定义pair类型的hash函数,即重载operator(),返回一个size_t类型,从而使得unordered_map支持用pair<>做为key值

struct pair_hash
{
    template<typename T1, typename T2>
    std::size_t operator() (const std::pair<T1, T2>& p) const {
        return std::hash<T1>{}(p.first) ^ std::hash<T2>{}(p.second);
    }
};

struct pair_equal
{
    template<typename T1, typename T2>
    bool operator() (const std::pair<T1, T2>& a, const std::pair<T1, T2>& b) const {
        return a.first == b.first && a.second == b.second;
    }
};

int main()
{
    unordered_map<pair<int, int>, int, pair_hash, pair_equal> m;

    return 0;
}

为了更加合理,我们还需要添加一个判断pair是否相等的函数,意在解决冲突。

最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容