在 C++ 中创建稀疏数组的最佳方法是什么？

我正在研究一个需要操作巨大矩阵的项目，特别是用于连接计算的金字塔求和。

简而言之，我需要跟踪矩阵（多维数组）中大量零的相对少量的值（通常为 1，在极少数情况下超过 1）。

稀疏数组允许用户存储少量值，并假设所有未定义的记录都是预设值。由于物理上不可能将所有值存储在内存中，因此我只需要存储少数非零元素。这可能是数百万个条目。

速度是一个巨大的优先级，我还想在运行时动态选择类中的变量数量。

我目前正在开发一个使用二叉搜索树（b 树）来存储条目的系统。有谁知道更好的系统吗？

对于 C++，映射效果很好。几百万个对象不会是问题。在我的计算机上，1000 万个项目大约需要 4.4 秒和大约 57 兆。

我的测试应用程序如下：

#include <stdio.h>
#include <stdlib.h>
#include <map>

class triple {
public:
    int x;
    int y;
    int z;
    bool operator<(const triple &other) const {
        if (x < other.x) return true;
        if (other.x < x) return false;
        if (y < other.y) return true;
        if (other.y < y) return false;
        return z < other.z;
    }
};

int main(int, char**)
{
    std::map<triple,int> data;
    triple point;
    int i;

    for (i = 0; i < 10000000; ++i) {
        point.x = rand();
        point.y = rand();
        point.z = rand();
        //printf("%d %d %d %d\n", i, point.x, point.y, point.z);
        data[point] = i;
    }
    return 0;
}

现在要动态选择变量的数量，最简单的解决方案是表示索引作为字符串，然后使用字符串作为地图的键。例如，位于 [23][55] 的项目可以通过“23,55”字符串表示。我们还可以将此解决方案扩展到更高的维度；例如对于三个维度，任意索引将类似于“34,45,56”。该技术的简单实现如下：

std::map data<string,int> data;
char ix[100];

sprintf(ix, "%d,%d", x, y); // 2 vars
data[ix] = i;

sprintf(ix, "%d,%d,%d", x, y, z); // 3 vars
data[ix] = i;