c++ - 在循环中执行移位操作时 C++ 中的内存泄漏

Question

我设法将问题简化为以下代码，该代码在我的笔记本电脑上运行时使用了近 500MB 内存 - 这反过来又导致整个程序中出现 std::bad_alloc。这里有什么问题？据我所知，无序映射仅使用 (32+32)*4096*4096 位 = 134.2MB 之类的内容，这与程序使用的内容相距甚远。

#include<iostream>
#include<unordered_map>

using namespace std;

int main()
{
    unordered_map<int,int> a;
    long long z = 0;

    for (int x = 0; x < 4096; x++)
    {
        for (int y = 0; y < 4096; y++)
        {
            z = 0;

            for (int j = 0; j < 4; j++)
            {
                    z ^= ((x>>(3*j))%8)<<(3*j);
                    z ^= ((y>>(3*j))%8)<<(3*j + 12);
            }

        a[z]++;
        }
    }
    return 0;
}

编辑:我知道这里的一些位移可能会导致未定义的行为，但我 99% 确定这不是问题所在。

EDIT2:我本质上需要的是计算给定集合中某个函数映射到第二个集合(大小为 4096*4096)中每个 y 的 x 的数量。将这些数字存储在数组中会更好吗？即我有一个函数 f: A 到 B，并且我需要知道 B 中每个 y 的集合 {x in A : f(x) = y} 的大小。在这种情况下，A 和 B 都是以下集合小于 2^12=4096 的非负整数。 (理想情况下我想将其扩展到 2^32)。

Answer 1

... which uses almost 500MB of memory ... What is the problem here?

关于您观察到的内存使用情况本身并没有真正的问题。 std::unordered_map 旨在快速运行大量元素。因此，内存并不是重中之重。例如，为了优化调整大小，它通常在创建时分配一些预先计算的 hash chains 。此外，您对元素计数乘以元素大小的测量并未考虑此映射中每个节点的实际内存占用(从数据结构角度来看)——这至少应该涉及一些指向相邻元素的指针in the list of its bucket .

话虽如此，目前还不清楚在这种情况下您是否需要使用 std::unorderd_map。相反，考虑到您尝试存储的映射定义为

{x in A : f(x) = y} for each y in B

你可以有一个固定大小的数组(使用std::array)，它只保存每个索引i，代表集合中的元素B，集合A中满足条件的元素数量。