c++ - 涉及 C++ 中图的大型测试用例（使用 STL）抛出 std::bad_alloc

Question

我们正在研究一个图（存储为邻接表实现）算法实现，它需要我们存储以下内容：

1. 二维 n 到 n 距离矩阵（存储为浮点数组）
2. 每对顶点之间的最短路径数（存储为整数数组）。
3. 对于所有可能的源选择，每个顶点的前辈都将给定顶点作为源顶点。这是 O(n*n*k)，其中 k 是源顶点的所有可能选择中所有顶点的平均前导数。在最坏的情况下，这可能是 O(n^3) 空间。然而，前辈的平均数量可能很小。（k 是一个常数）。Predecessor 存储为两级映射，前驱列表存储为 STL 向量。

我们尝试在大图（>2^12 个顶点）上进行测试，运行一段时间后会抛出 std::bad_alloc。即使在仅使用 3GB 内存的 8GB（Ubuntu 12.04）或 16GB 上运行时也是如此。你能告诉我们如何让大型测试用例工作还是我们在某个地方出错了？

Answer 1

尝试在 64 位操作系统上以 64 位模式编译代码。