c++ - 从到严格增加值的元素的映射的内存使用情况

Question

map 的数据结构和用途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;

map 的属性

映射的第一个元素的 sum始终为1。对于以下每个元素，始终，其6个属性( a， b， c， d， e或 f)中的一个值仅增加了1换句话说，以下关于 map 的断言始终是正确的

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。

有没有一种方法可以创建一个 map ，该 map 允许恒定时间访问 i和 a， b， c， d， e或 f之间的匹配而不会占用太多RAM？

Answer 1

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

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

您将需要调整快照的步长，但是，只要使用恒定数字，就可以进行O(1)查找。