此问题适用于任何类型的静态数据.我只使用int来保持示例简单.
我正在读取包含整数的大型XML数据文件,并将它们存储在向量< int>中.对于我正在使用的特定数据,相同的值连续重复多次是很常见的.
<Node value="4" count="4000">
count属性表示该值要重复x次：
for(int i = 0; i < 4000; i++)
vec.push_back(4);
当我已经知道它将连续出现4000次时,重复存储相同值似乎是浪费内存.但是,我需要能够在任何时候索引到向量.
对于较大的数据对象,我知道我只能存储一个指针,但仍然需要在上面的例子中存储4000个相同的指针.
是否有任何类型的策略来处理这样的问题？
解决方法
使用两个向量.第一个向量包含索引,第二个向量包含实际值.
填写索引向量,使得索引[i-1]和indices [i]之间的所有索引的值都在值[i]中.
然后在indices数组上使用二进制搜索来定位values数组中的位置.二进制搜索非常有效(O(log n)),与原始方法相比,您只会使用一小部分内存.
如果您假设以下数据：
4000 ints with value "4" followed by 200 ints with value "3" followed by 5000 ints with value "10"
您将创建一个索引向量和值向量,并填充如下：
indices = {4000,4200,9200}; // indices[i+1] = indices [i] + new_count or 0
values = {4,3,10};
正如其他答案中所建议的那样,你应该将它包装在operator []中.
