多维数组 - 用于在C++中存储非常大的 2D 数据的数据结构

Question

我需要处理最多 1 亿行和 30 列的数据表 （2D）。表元素仅包含 0、1 和短划线 （-）。该表以文本文件的形式提供给我。我必须将这些数据存储到一些数据结构中，并执行排序表、删除行、比较元素（在不同的行和列中）等操作。

目前我正在为此使用 2D 矢量。我尝试使用整数向量和位向量。两者都适用于 10mil 行和 25 列，但都不适用于上述最大限制（我有一个糟糕的分配）。

我假设这是因为向量需要连续内存。对此的正确数据结构是什么？时间也是我的考虑因素之一，并且也希望访问时间较短。另外，如果向量实际上是正确的数据结构，我可以使用更好的实现来使其工作吗？我必须坚持C++，不能使用数据库和其他东西。

多谢！

Answer 1

查看 Nstate。

它是任意基数的打包数组库（因此三态符合条件）。

http://nstate.hostilefork.com

免责声明：我写了 nstate。

Answer 2

你可以考虑一个boost::tribool数组

看

• http://www.boost.org/doc/libs/1_55_0/doc/html/tribool.html
• 针对空间优化摩擦波阵列

您还可以考虑在std::bitset上使用包装器，以便每个摩擦函数在位集中有 2 位。

尺寸N的tribool需要尺寸bitset 2*N

映射：

tribool(i) maps to bitset(2*i) and bitset(2*i+1)
if tribool(i) == indeterminate, then bitset(2*i) = false
if tribool(i) == true, then bitset(2*i) = true, bitset(2*i) = true
if tribool(i) == false, then bitset(2*i) = true, bitset(2*i) = false

C++伪代码：

template<size_t N>
class PackedTribool {
public:
  ??? test( i ) {
    if( bits_[ 2 * i ] == false ) {
        return indeterminate;
    }
    else {
        return( bits_[ 2 * i + i ];
    }
  }
private:
  std::bitset<2*N> bits_;     // note: size is doubled
};