在循环中执行移位操作时 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：我基本上需要计算给定集合中 x 的数量，某些函数映射到第二组（大小为 4096 * 4096）中的每个 y。将这些数字存储在数组中会更好吗？即我有一个函数 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. Also, your measure of the the count of elements multiplied by the element's size is not taking into account the actual memory-footprint, data structure-wise, of each node in this map -- which should at least involve a few pointers to adjacent elements .

话虽如此，但您甚至不清楚在这种情况下是否需要使用 std::unorderd_map。相反，给定您的尝试商店的映射定义为

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

你可以有一个固定大小的数组（为此使用 std::array），它只包含每个索引 i，代表集合 B[=25 中的元素=]，集合 A 中满足条件的元素数。

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

Memory leak in C++ when performing shift operations in loop

c++

memory-leaks

unordered-map

bit-shift