c++ - 是否可以在 64 位系统中使用 C++11 为图形创建位邻接数组

Question

是否可以在 64 位系统中使用 c++11 为图形创建位邻接数组

我需要部署一个大图，比如 N=10000000。但是编译器不允许我定义一个二维的大尺寸数组，比如 Adj[N][N]。我只部署权重为0的图。如果两个节点有链接，则Adj[N][N]对应的元素为1，否则为0。所以我只需要一位来做到这一点。我想知道是否可以使用一个长位内存来存储一个位数组来描述一个二维数组。

例如:

16 位数组的 4X4 邻接矩阵:1010010100110110

所以元素1,1为1,元素1,2为0,......,元素4,4为0

我需要位操作来找到我需要部署的元素。

问题是如何做到这一点？如何在内存中分配一个长的连续位存储？ malloc？如何定义指针？空类型？

编辑

假设 10000000。unsigned char 可能需要 90T 内存。我知道有人部署了 10^7 个节点。也许他们正在使用动态分配内存的 vector 或列表。

Answer 1

你需要一个“稀疏数组”，其中实际上只填充了几个元素。我会首先想到使用 std::map，像这样:

#include <map>
class MyNode {
// your stuff here
};
typedef <your node id type> MyNodeId; // must naturally or by overload define an operator <

typedef std::map<MyNodeId, MyNode> ArcsFromNode;

typedef std:map<MyNodeId, ArcsFromNode> MyGraph;