与向量一起使用时,C++ unordered_map失败

Question

背景:我是从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退出状态

知道问题的根源吗？

提前致谢.

Answer 1

§23.2.5,第3段说:

每个无序关联容器Key由一个Hash满足Hash要求(17.6.3.4)的函数对象类型参数化Key,并作为类型参数值的哈希函数,并通过二元谓词Pred在类型值上引入等价关系Key.

使用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.但是,请避免使用散列无序容器,因为不同的订单会产生不同的散列,并且无法保证无序容器中的顺序.}

Answer 2

我发现R. Martinho Fernandes的答案不适合竞争性编程，因为在大多数情况下，您必须使用提供的IDE，并且不能使用外部库boost。如果您想充分利用STL，可以使用以下方法。

如上所述，您只需要编写一个哈希函数。而且它应该专门用于存储在向量中的数据类型。以下哈希函数假定int类型数据：

struct VectorHasher {
    int operator()(const vector<int> &V) const {
        int hash=0;
        for(int i=0;i<V.size();i++) {
            hash+=V[i]; // Can be anything
        }
        return hash;
    }
};

请注意，您可以使用任何类型的操作来生成哈希。您只需要有创造力，以使冲突最小化。例如hash^=V[i]，hash|=V[i]，hash+=V[i]*V[i]甚至hash+=(V[i]<<i)*(V[i]<<i)*(V[i]<<i)都是有效的，直到当然，你的哈希值不溢出。

最后，将此哈希函数与your一起使用，请unordered_map按如下所示对其进行初始化：

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