在 C++ 中创建无序映射以计算对数

Question

所以假设我有一个数组 1 2 1 2 3 4 2 1 我想存储所有 (arr[i], arr[i-1) 这样 arr[i] != arr[i-1] 作为一对 unordered_map 来计算这些对.
例如

(1, 2)  -> 2
(2, 3) -> 1
(3, 4) -> 1
(4, 2) -> 1
(2, 1) -> 1

所以我试过的语法，

unordered_map<pair<int, int>,  int> umap;
int temp; 
cin>>temp;
arr[i]=temp;
for (int i=1; i< n; i++){
   cin>>temp;
   arr[i]=temp;
            
   umap[(arr[i-1], arr[i])]++;
}

接下来，我也尝试了正确的定义。

unordered_map<pair<int, int>,  int> umap;
cin>>temp;
arr[i]=temp;
for (int i=1; i< n; i++){
   cin>>temp;
   arr[i]=temp;
   pair<int, int> p(arr[i-1], arr[i]);
   umap[p]++;
}

任何人都可以帮助我获得正确的语法吗？

Answer 1

您不能只将 unordered_map 与 pair 一起使用，因为没有实现默认哈希。但是，您可以使用 map，它应该可以很好地满足您的目的，因为 pair 确实实现了 <。当您真正想要 unordered_map 时，请参阅。

你可以像这样用花括号构造pair

umap[{arr[i-1], arr[i]}]++;

我想从 C++11 开始，但它可能是 C++14 甚至 C++17

Answer 2

这种情况下的问题是 std::unordered_map 需要可散列的键类型。（它是作为哈希图实现的）

但是 std::hash 没有 std::pair<> 的重载，所以你的 std::unordered_map 没有编译。

使用正常 `std::map`

您可以通过切换到只需要 operator< 的法线贴图来解决此问题，其中 is implemented by std::pair:

std::map<std::pair<int, int>,  int> umap;

int values[] = {1, 2, 1, 2, 3, 4, 2, 1};
for (int i=1; i< sizeof(values) / sizeof(int); i++) {
    umap[std::pair(values[i-1], values[i])]++;
}

godbolt example

创建哈希函数

或者如果你想保留哈希图，你需要为你的对提供一个哈希函数，例如：

struct pair_hash
{
    template <class T, class U>
    std::size_t operator()(std::pair<T, U> const& pair) const {
        return std::hash<T>()(pair.first) ^ std::hash<U>()(pair.second);
    }
};

然后将其用于您的地图：

std::unordered_map<std::pair<int, int>,  int, pair_hash> umap;

int values[] = {1, 2, 1, 2, 3, 4, 2, 1};
for (int i=1; i< sizeof(values) / sizeof(int); i++) {
    umap[std::pair(values[i-1], values[i])]++;
}

godbolt example

警告： 在这个例子中，对中的两个散列只是异或。一般来说，这不是一个很好的组合哈希的方法，您应该用更好的函数替换它以供生产使用，例如 this hash_combine function.

在 C++ 中创建无序映射以计算对数

Creating unordered map in C++ for counting the pairs

c++

stl

使用正常 `std::map`

创建哈希函数

在 C++ 中创建无序映射以计算对数

Creating unordered map in C++ for counting the pairs

c++

stl

使用正常 std::map

创建哈希函数

使用正常 `std::map`