c++ - 优化动态大小 vector 的 vector 存储

Question

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

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

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

vector<vector<item>> vss;

使用这种方法，内部 vector 中的内存分配将无处不在。迭代 vss 中的所有元素在缓存方面会很困惑，这可能会导致性能问题。

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

假设无法预先确定内部 vector 的大小，是否有一种方法可以构造和填充 vss，以便迭代元素不会造成缓存灾难？

谢谢。

Answer 1

我只是想添加我当前的但希望是临时的解决方案。而不是填写 vss直接地，我使用一个临时 vector 对:

vector<pair<size_t, item>> temporaries;

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