algorithm - C++ std::unordered_map 键自定义散列

Question

我有以下test.cpp 文件

#include <string>
#include <functional>
#include <unordered_map>
#include <iostream>

class Mystuff {
public:
   std::string key1;
   int key2;
public:
    Mystuff(std::string _key1, int _key2) 
        : key1(_key1)
        , key2(_key2)
    {}
};

namespace std {
template<>
struct hash<Mystuff *> {
    size_t operator()(Mystuff * const& any) const {
        size_t hashres = std::hash<std::string>()(any->key1);
        hashres ^= std::hash<int>()(any->key2);
        std::cout << "Hash for find/insert is [" << hashres << "]" << std::endl;
        return (hashres);
    }
};
}; /* eof namespace std */

typedef std::unordered_map<Mystuff *, Mystuff *>mystuff_map_t;

mystuff_map_t map;

int insert_if_not_there(Mystuff * stuff) {
    std::cout << "Trying insert for " << stuff->key1 << std::endl;
    if (map.find(stuff) != map.end()) {
        std::cout << "It's there already..." << std::endl;
        return (-1);
    } else {
        map[stuff] = stuff;
        std::cout << "Worked..."  << std::endl;
    }
    return (0);
}

int main(){
    Mystuff first("first", 1);
    Mystuff second("second", 2);
    Mystuff third("third", 3);
    Mystuff third_duplicate("third", 3);

    insert_if_not_there(&first);
    insert_if_not_there(&second);
    insert_if_not_there(&third);
    insert_if_not_there(&third_duplicate);

}

您可以使用 g++ -o test test.cpp -std=gnu++11 进行编译。

我不明白我做错了什么:哈希键控算法确实有效，但出于某种原因(这显然是我做某事的 - 糟糕 - 方式)，third_duplicate 也被插入到 map 中，但我希望它不是。

我做错了什么？

Answer 1

IIRC 无序容器需要 operator==以及std::hash .没有它，我预计会出现编译错误。除了你的 key 实际上是 MyStuff* - 指针，而不是值。

这意味着您将重复的 key 存储为一个单独的项目，因为它实际上不是，unordered_map ，一个真正的副本 - 它有一个不同的地址，地址相等是如何 unordered_map正在判断平等。

简单的解决方案 - 使用 std::unordered_map<Mystuff,Mystuff>反而。您将需要重载 operator== (或者有一些类似于 std::hash 的 IIRC 替代模板，您可以对其进行专门化)。您还需要更改您的 std::hash也接受值而不是指针。

不要在 C++ 中过度使用指针，尤其是原始指针。对于按引用传递，更喜欢对指针的引用(这是“引用”与“指针”的 C++ 特定含义)。对于容器，正常默认情况下直接使用内容类型，但在某些情况下您可能需要指针(或智能指针)。

我没有彻底检查您的代码 - 问题可能比我发现的要多。