优化动态调整大小的向量的向量存储

Question

在我正在做的一些工作中，我多次遇到这种问题模式，我想知道是否存在一个已知的解决方案。

这很简单:我有一个元素的向量，而这些元素又是一些动态大小的向量。我知道内部向量的大小将相对较小(即，在平均情况下，项目的数量级为10)，但它们将会很多。

我可以天真地解决这个问题：

vector<vector<item>> vss;

使用这种方法，内部向量中的内存分配将会到处都是。迭代vss中的所有元素将会在缓存方面变得一团糟，这可能会导致性能问题。

我认为这可以使用某种链表结构来解决，在相同的内存块中有多个头。

假设内部向量的大小不能预先确定，有没有一种方法可以构造和填充vss，这样迭代元素就不会成为缓存灾难？

谢谢。

Answer 1

我只想添加我目前的，但希望是暂时的解决方案。我没有直接填充vss，而是使用了一个临时的配对向量：

vector<pair<size_t, item>> temporaries;

，这表示应该在特定索引处插入某些项。从这里开始，我计算每个索引的条目数，分配单个内存块来保存这些条目，并移动数据。一些额外的向量用于记账(即每个索引的项目数及其起始位置)。