C++中使用vector作为键时，unordered_map失败

Question

C++中使用vector作为键时，unordered_map失败

28

背景：我来自Java世界，对于C++或Qt还比较陌生。

为了尝试使用unordered_map，我编写了以下简单程序：

#include <QtCore/QCoreApplication>
#include <QtCore>
#include <iostream>
#include <stdio.h>
#include <string>
#include <unordered_map>

using std::string;
using std::cout;
using std::endl;
typedef std::vector<float> floatVector;

int main(int argc, char *argv[]) {
    QCoreApplication a(argc, argv);
    
    floatVector c(10);
    floatVector b(10);
    
    for (int i = 0; i < 10; i++) {
        c[i] = i + 1;
        b[i] = i * 2;
    }
    
    std::unordered_map<floatVector, int> map;
    
    map[b] = 135;
    map[c] = 40;
    map[c] = 32;
  
    std::cout << "b -> " << map[b] << std::endl;
    std::cout << "c -> " << map[c] << std::endl;
    std::cout << "Contains? -> " << map.size() << std::endl;
    
    return a.exec();
}

很不幸，我遇到了以下错误，这并没有给我太多启示。甚至没有行号。

:-1: 错误：collect2：ld 返回 1

您有任何关于问题起源的想法吗？

- Pierre-Antoine

2

你需要一个接受 vector<float> 的哈希函数。 - Seth Carnegie

3

这不是运行时故障。 - R. Martinho Fernandes

@SethCarnegie 我原本认为问题就是这个。然而，对我来说，像 vector 这样基础的类应该有一个默认的哈希函数。如果不是这种情况，你能否解释一下如何提供一个或者指向一些资料。谢谢！ - Pierre-Antoine

1

有意思且合法的问题，但我不认为有任何使用情况是聪明的将列表用作映射中的键。 - UmNyobe

1

@UmNyobe，int是从向量作为输入进行重计算的结果。一旦计算完成，需要快速多次访问结果。 - Pierre-Antoine

2个回答

23

我认为R. Martinho Fernandes的回答不太适用于竞赛编程，因为大多数情况下你必须使用提供的IDE，并且不能使用外部库，如boost。如果您想充分利用STL，则可以使用以下方法。

如上所述，您只需要编写哈希函数，并对存储在向量中的数据进行特殊化。下面的哈希函数假定数据类型为int：

struct VectorHasher {
    int operator()(const vector<int> &V) const {
        int hash = V.size();
        for(auto &i : V) {
            hash ^= i + 0x9e3779b9 + (hash << 6) + (hash >> 2);
        }
        return hash;
    }
};

请注意，您可以使用任何类型的操作来生成哈希。只需要创造性地减少冲突。例如，hash^=V[i]，hash|=V[i]，hash+=V[i]*V[i]或者hash+=(V[i]<<i)*(V[i]<<i)*(V[i]<<i)都是有效的，当然，只要您的哈希不溢出即可。

最后，要使用此哈希函数与您的unordered_map，请按以下方式初始化：

unordered_map<vector<int>,string,VectorHasher> hashMap;

- Chirag Arora

1

第二个模板参数应该是 int 而不是 bool，对吗？ - wcochran

@wcochran 它可以与任何允许的数据结构/类型一起使用（map、vector、set、queue、stack、int、float等）。这取决于您的用例。 - Chirag Arora

如果您不介意使用一个合理的哈希函数，为什么不直接使用 template <typename T> struct AnyHasher { int operator()(const T &) { return 0; } } 呢？ - Caleth

@Caleth，你现在认为它足够合理了吗？ - Chirag Arora

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- R. Martinho Fernandes · Accepted Answer

根据§23.2.5第3段的规定：

每个无序关联容器都由参数化的，满足Hash要求（17.6.3.4）且作为类型的参数值的哈希函数的函数对象类型，以及导致类型的值之间存在等价关系的二元断言组成。

如果使用vector<float>作为Key，并且没有提供显式的哈希和等价谓词类型，则将使用默认的std::hash<vector<float>>和std::equal_to<vector<float>>。

对于等价关系的std::equal_to是可以的，因为向量有一个运算符==，这就是std::equal_to所使用的内容。

然而，没有std::hash<vector<float>>专业化，这可能是您没有向我们展示的链接器错误。您需要提供自己的哈希函数才能使其正常工作。

编写此类哈希函数的简单方法是使用boost::hash_range。

template <typename Container> // we can make this generic for any container [1]
struct container_hash {
    std::size_t operator()(Container const& c) const {
        return boost::hash_range(c.begin(), c.end());
    }
};

然后你可以使用：

std::unordered_map<floatVector, int, container_hash<floaVector>> map;

当然，如果您需要在地图中使用不同的相等语义，您需要适当地定义哈希和等价关系。

_{1. 但是，在为无序容器进行哈希处理时应避免这样做，因为不同的顺序将产生不同的哈希值，并且无序容器中的顺序不能保证。}