c++ - 冗余静态数据

Question

这个问题适用于任何类型的静态数据。我只使用 int使示例保持简单。

我正在读取一个包含整数的大型 XML 数据文件并将它们存储在 vector<int> 中.对于我使用的特定数据，相同的值连续重复多次是很常见的。

<Node value="4" count="4000">

count属性表示该值要重复 x 次:

for(int i = 0; i < 4000; i++)
    vec.push_back(4);

当我已经知道它会连续出现 4000 次时，重复存储相同的值似乎是在浪费内存。但是，我需要能够随时索引到 vector 中。

对于较大的数据对象，我知道我可以只存储一个指针，但在上面的示例中这仍然需要存储 4000 个相同的指针。

是否有任何类型的策略来处理此类问题？

Answer 1

使用两个 vector 。第一个 vector 包含索引，第二个包含实际值。

填写索引 vector ，使索引[i-1]和索引[i]之间的所有索引的值都在值[i]中。

然后对索引数组使用二分查找来定位值数组中的位置。二进制搜索非常有效 (O(log n))，与原始方法相比，您只会使用一小部分内存。

如果假设以下数据:

4000 ints with value "4"
followed by 200 ints with value "3"
followed by 5000 ints with value "10"

您将创建一个索引 vector 和值 vector 并像这样填充它:

indices = {4000, 4200, 9200}; // indices[i+1] = indices [i] + new_count or 0
values = {4,3,10};

正如其他答案中所建议的，您可能应该将其包装在运算符 [] 中。