我的程序需要一个哈希Map,它的输入是由两个三维坐标定义的范围(int start[3]
,int stop[3]
),输出是一个动态整数数组,定义为std::vector<int>
。为了实现这个哈希表,我将std::tuple<int*, int*>
声明为一个名为CoordsKey
的自定义类型。然后,我重新实现了operator()
,以根据start[3]
和stop[3]
计算哈希值(为了快速原型化,我简单地根据int *start
和int *stop
的值创建了一个std::tuple<int, int, int, int, int, int>
,因此它可以通过Boost进行哈希)。
#include <iostream>
#include <tuple>
#include <unordered_map>
#include <boost/container_hash/extensions.hpp>
using CoordsKey = std::tuple<int*, int*>;
struct CoordsKeyHash {
std::size_t operator()(const CoordsKey& key) const
{
/* std::tuple is hashable by Boost */
std::tuple<int, int, int, int, int, int> t = {
std::get<0>(key)[0], std::get<0>(key)[1], std::get<0>(key)[2],
std::get<1>(key)[0], std::get<1>(key)[1], std::get<1>(key)[2]
};
auto hash = boost::hash_value(t);
fprintf(stderr, "access (%d, %d, %d)-(%d, %d, %d) with hash %ld\n",
std::get<0>(key)[0], std::get<0>(key)[1], std::get<0>(key)[2],
std::get<1>(key)[0], std::get<1>(key)[1], std::get<1>(key)[2],
hash
);
return hash;
}
};
using CoordsMap = std::unordered_map<CoordsKey, std::vector<int>, CoordsKeyHash>;
然后,可以使用以下代码访问该哈希Map:
int start[3] = {1, 2, 3};
int end[3] = {4, 5, 6};
auto& vec = map[std::make_tuple(start, end)];
不幸的是,我发现修改这个哈希Map中的向量没有效果,它的内容在函数返回后消失,如下面的演示所示:
#include "CoordsMap.h"
CoordsMap map;
void test(void)
{
int start[3] = {1, 2, 3};
int end[3] = {4, 5, 6};
map[std::make_tuple(start, end)] = std::vector<int>();
map[std::make_tuple(start, end)].push_back(8);
map[std::make_tuple(start, end)].push_back(9);
fprintf(stderr, "vec size %ld\n",
map[std::make_tuple(start, end)].size()
);
}
int main(void)
{
int start[3] = {1, 2, 3};
int end[3] = {4, 5, 6};
test();
auto& vec = map[std::make_tuple(start, end)];
fprintf(stderr, "main(): vec size %ld\n", vec.size());
for (auto& i : vec) {
std::cout << i << std::endl;
}
}
运行此程序后,输出为:
access (1, 2, 3)-(4, 5, 6) with hash 3332428396118021859
access (1, 2, 3)-(4, 5, 6) with hash 3332428396118021859
access (1, 2, 3)-(4, 5, 6) with hash 3332428396118021859
access (1, 2, 3)-(4, 5, 6) with hash 3332428396118021859
vec size 2
access (1, 2, 3)-(4, 5, 6) with hash 3332428396118021859
main(): vec size 0
可以看到,从test()
返回后,向量中修改的内容已经消失,即使使用完全相同的哈希值来访问其内容。我不确定这里发生了什么,但症状看起来类似于尝试在堆栈上使用不存在的局部变量时会发生的情况。
奇怪的是,如果使用一个简单的int
作为密钥,同样的问题不会发生:
#include <iostream>
#include <vector>
#include <tuple>
#include <unordered_map>
using IntegerMap = std::unordered_map<int, std::vector<int>>;
IntegerMap map;
void test(void)
{
map[42].push_back(8);
map[42].push_back(9);
fprintf(stderr, "vec size %ld\n",
map[42].size()
);
}
int main(void)
{
test();
auto& vec = map[42];
fprintf(stderr, "main(): vec size %ld\n", vec.size());
for (auto& i : vec) {
std::cout << i << std::endl;
}
}
第二个程序的输出是:
vec size 2
main(): vec size 2
8
9
提问
第二个程序有效,但第一个不行,为什么?我错在哪里?
1条答案
按热度按时间mspsb9vt1#
尽管您提供了一个适当的散列函数,但是对于无序容器,默认的相等比较函数仍然是默认的。这意味着,实际上,指针本身将被比较。
这可能不会像你想的那样。指向相同
int
值的两个不同指针不会被比较为相等,因为它们是不同的。这不太可能是你预期的结果。但这是你最小的麻烦。
对于散列函数和相等比较函数(无论如何实现),这显然意味着这些指针***必须保持有效***。
这似乎是
int
值,将形成您的密钥之一。这两个对象
start
和end
将在test()
返回时超出作用域并被销毁。但它们将被用作无序Map中的底层指针。
因此,
test()
返回后,使用unordered_map
将成为未定义的行为。这些int
值将不再存在。Map键中的基础指针将指向已销毁的对象。有一个名字来形容导致所有这些麻烦的潜在问题,它被称为“指针的无意义使用”。用
std::tuple<std::vector<int>,std::vector<int>>
替换容器的密钥可能会解决所有问题。