用于从映射到严格增加值的元素的内存使用量

Question

地图M的数据结构和用途] >>

在我的代码中，我有一个称为M的地图，定义为

class T
{
public:
    size_t a;
    size_t b;
    size_t c;
    size_t d;
    size_t e;
    size_t f;

    size_t sum()
    {
        return a+b+c+d+e+f;
    }
}

const std::vector<T> M;
M是const。它是在较长过程的开始时构建的，然后仅用于读取索引i与值a，b，c，d，e和f之间的匹配]。例如
auto& c = M[i].c;
地图属性

映射的第一个元素的sum始终为1。对于随后的每个元素，始终只有6个属性（a，b，c，d ，e或f）的值正好增加了1。换句话说，以下有关映射的断言始终为真]

if (i < M.size())
{
   if (i >= 0)
       assert(M[i].sum() == i+1);

   if (i > 0)
   {          
       assert(M[i].sum() - M[i-1].sum() == 1);
       assert(M[i].a == M[i-1].a || M[i].a == M[i-1].a + 1);
       assert(M[i].b == M[i-1].b || M[i].b == M[i-1].b + 1);
       assert(M[i].c == M[i-1].c || M[i].c == M[i-1].c + 1);
       assert(M[i].d == M[i-1].d || M[i].d == M[i-1].d + 1);
       assert(M[i].e == M[i-1].e || M[i].e == M[i-1].e + 1);
       assert(M[i].f == M[i-1].f || M[i].f == M[i-1].f + 1);
   }
}
问题和问题

此系统直到最近才运行良好，因为我现在需要M的长度为5e8，这最终会占用很多不必要的RAM。

有没有一种方法，我可以创建一个映射，该映射允许恒定时间访问i与a，b，c，d，e或f之间的匹配占用这么多RAM？

地图M的数据结构和用法在我的代码中，我有一个名为M的地图，定义为类T {public：size_t a; size_t b; size_t c; size_t d; size_t e; size_t f; size_t ...

Answer 1

如果您知道先前的值，则足以了解哪个变量增加了一个。由于它们有六个（a，b，c，d，e，f），因此可以用3位表示该信息。对于n条目，您总共需要3 * n位。

就大小而言，这是一种改进，但是它将违反您的常量访问限制，因为您需要为每个查找迭代所有先前的条目。但是您可以权衡速度与内存，但可以存储快照。例如，如果将快照保留在100个元素之后，则在最坏的情况下，您将必须遍历最后100个条目。那仍然是O(1)。