23

背景：我来自 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 退出状态

知道问题的根源吗？

4

2 回答 2

36

§23.2.5，第 3 段说：

每个无序关联容器由满足哈希要求 (17.6.3.4) 并充当类型参数值的哈希函数Key的函数对象类型以及在类型值上引发等价关系的二元谓词参数化。HashKeyPredKey

使用vector<float>asKey而不提供显式哈希和等价谓词类型意味着默认值std::hash<vector<float>>并将std::equal_to<vector<float>>被使用。

std::equal_tofor 等价关系很好，因为有一个向量的运算符，==这就是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. 但是，对于无序容器的哈希，请避免这种情况，因为不同的订单会产生不同的哈希，并且无序容器中的顺序不能保证。

于 2012-05-01T22:13:25.297 回答
18

我发现 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;
于 2018-11-13T15:11:25.643 回答