c++ - 初始化向量向量

Question

我正在使用一个

vector<vector<size_t>> Ar;

结构体。结构的内容随时间变化，特别是每个嵌套向量的长度是随机的并且随时间变化。顺序很重要，如果嵌套向量为空，我不能忽略它。我知道嵌套向量（比如 m）和外部向量（比如 n）的最大容量。

我在初始化正确时遇到了一些困难。如果我使用

Ar(n);

没有问题，但我最终得到了内存碎片，因为分配器不知道嵌套向量的大小。如果可能的话，我想避免这种情况，因为我不知道随着我试图处理的数据大小的增加，它会产生什么影响。我试图通过提前固定嵌套向量的长度来解决碎片以获得紧凑的表示，但我在这样做时遇到了麻烦。我用

Ar(n,vector<size_t>(m));

但这超级慢并且会大量浪费内存，因为大多数条目都不会被使用。

我已经成功地实现了这一点

vector<list<size_t> > Ar(n);

不会产生碎片，但它的运行速度比使用嵌套向量要慢得多。像 Boost::multi_array 这样的固定表示会占用太多空间，原因与上面的第二个初始化相同，并且实现起来会更加困难，因为我需要跟踪有用条目的停止位置。

有什么建议么？提前致谢。

Answer 1

在使用典型用例分析代码之前，您不知道内存碎片是否是一个问题。除非m前面非常小，否则n我认为它根本不会成为瓶颈，因为您仍然有大部分顺序内存访问。

如果你想避免它，你可以使用对象reserve来代替resize或初始化m。它只会分配内存，没有构造不会使用的对象的开销，从而提高了初始化速度。

此外，reserve在您有效使用它之前，向量的容量可能只会消耗虚拟内存，而不是“真实”内存。

如果你知道内部向量大小的分布，使用平均值作为默认长度，它可以帮助你减少内存的浪费。

无论如何，std::list这是一个更大的空间浪费，考虑到碎片化，情况会更糟。

Answer 2

也许该resize功能会对您有所帮助。有关详细信息，请参见此处。