c++ - 有效地动态存储具有许多零的矩阵

Question

背景：

我在c++中工作。

我记得有一种方法可以有效地（内存方面）存储“数组”（数组可能由std::vector's、std::set's 等组成......我不在乎如何，只要它是内存高效的并且我能够检查0's和1's（或等效地，真/假等）的每个元素的值，其中一个或另一个的数量不成比例（例如，大部分为零）。

---

我编写了一个算法，它根据某个函数填充一个“数组”（目前是a ）vector<vector<size_t>>。出于这些目的，我们或多或少可以认为它是随机完成的。该数组将非常大（可变大小......按列和或更多行的顺序），并且始终为矩形。0's1's10001E+8

需要有这么多数据点。在最好的情况下，我的机器很快就会变得资源受限并且慢到爬行。在最坏的情况下，我得到std::bad_alloc.

撇开我打算用这个数组做什么，存储和（或/等）的矩形数组最有效（内存方面）的方法是什么，其中大部分是's 或's （我知道哪个人口最多）？1's0'sTF10.

请注意，数组需要“动态”创建（即一次一个元素），元素必须保持其位置，并且我只需要在创建后检查单个元素的值。我担心内存占用，仅此而已。

标签： c++arraysoptimization

Answer 1

这称为稀疏数组或矩阵。

std::set<std::pair<int,int>> bob;

如果您希望 7,100 为 1，只需bob.insert({7,100});. 缺少的元素为 0。bob.count({3,7})如果您愿意，可以使用 0/1 值。

现在循环遍历两列是行是棘手的；最简单的方法是每组倒着做 2 组。

如果您不需要按顺序循环，请改用无序集。