C++的std :: unordered_map键定制散列
问题描述:
我有以下test.cpp
文件C++的std :: unordered_map键定制散列
#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
以及在地图中,而我希望它不是。
我在做什么错?
答
IIRC无序容器需要operator==
以及std::hash
。没有它,我期望编译错误。除了你的密钥实际上是MyStuff*
- 指针,而不是值。
这意味着你得到的重复密钥存储为一个单独的项目,因为它实际上不是unordered_map
,一个真正的重复项 - 它具有不同的地址,并且地址相等是如何判断是否相等。
简单的解决方案 - 使用std::unordered_map<Mystuff,Mystuff>
来代替。您需要重载operator==
(或者有IIRC一些替代模板,类似于std::hash
,您可以专注)。您还需要将您的std::hash
更改为接受值而不是指针。
不要过度使用C++中的指针,特别是不要使用原始指针。对于传递引用,更喜欢引用指针(这是C++特定的“引用”与“指针”的含义)。对于容器,正常的默认设置是直接为内容使用类型,尽管有些情况下你可能需要一个指针(或一个智能指针)。
我还没有彻底检查你的代码 - 可能会有更多的问题比我抓到的。
我相信你确实指出了这个问题..请确认我的想法: 你只是不能定义'bool operator ==(Mystuff *,Mystuff *)'这样的东西,因为'必须有一个类或枚举类型的参数'。动机是,通过定义上述内容,您拒绝使用实际指针的地址值进行比较的能力,这是地图中插入关键字冲突所需的值。 事实上,我的示例中发生的事情正好是哈希键匹配,因此插入函数通过它们的地址比较对象并插入它们,而不考虑键匹配。 –
@RiccardoManfrin - 你不能定义'bool operator ==(MyStuff *,MyStuff *)',因为它已经存在。它比较*指针* - 即地址 - 是否相等。指针的比较是从C继承而来的,对所有的指针类型都是一样的,甚至是那些不能用C存在的类型。你需要定义的是'bool operator ==(MyStuff,MyStuff)'或'bool operator = =(const MyStuff&,const MyStuff&)' - 值相等,或者传递值或者传递const引用。 – Steve314
C++中的所有参数都是按值传递的。当你传递一个指针时,你是通过值来传递指针的 - 这个函数应该被看作与指针一起工作,并且只能通过间接的指向值来进行。即使引用参数是通过值传递的引用类型的值,但是您并不直接使用引用(因为它的自解引用),因此将其视为通过引用传递值更直观。尽管这不是严格正确的,但引用类型可以用于其他事物,并且将它们用于参数并不会做任何特殊的事情。 – Steve314