矢量矢量作为高效的数据结构; std :: vector <std :: vector <someType >>的替代品

Question

我正在寻找数据结构,我可以在一个向量中存储多个向量,而不会有碎片或任何性能问题.

现在这样做

std::vector< std::vector<SomeType> > myMultiVector;

会有所帮助,但是根据我的理解,内存会碎片化,因为myMultiVector中的每个向量都不会位于连续的空间中,因为它的分配方案.

这不是用于创建从一开始就知道尺寸或尺寸的阵列.各个方向的尺寸都是动态的.我想要的是一个像那样的结构,其中分配的大小是连续的.我希望能够在向量向量和每个向量本身上执行类似push_back()和resize()的操作.矢量的大小应该能够不同.

我一直在看看Boost :: Multiarray.似乎有希望,但不想要一个阵列,我想要一些dyanmic的东西.我仍然不确定,但如果我能以有效的方式改变尺寸,我可以改变尺寸.也许Boost :: Multiarray就是答案.

我也一直在考虑使用std :: multimap甚至std :: unordered_multimap并使用密钥作为索引,因为内部排序和散列我不确定它是否是正确的结构,尽管分配空间应该是连续的.

使用std :: vector <std :: vector> myMultiVector; 适用于我需要的东西,但我觉得有一个错过优化的机会.

您知道哪些其他替代品可以帮助提供更有效的载体载体？让我知道 :-)

注意:我知道问题与此处提出的问题非常相似.我只是要求替代方案不能解决特定问题.

Answer 1

这听起来像你想要的不同东西相互排斥.如果你想在每个子向量中具有大小灵活性,同时让所有数据在内存中很好地对齐,你基本上被迫为所有向量重新分配内存,并在每次更改大小时进行大量复制任何子向量.因此,可能最好留下来std::vector< std::vector<SomeType> >.如果你需要做大量的高效运营的每间向量的一个固定大小的调整操作,你可以考虑创建到你复制所有数据的中间阵列.

您还应该考虑您对绩效的担忧是否会在实践中产生影响.除非您注意到使用std::vector< std::vector<SomeType> >确实会显着影响您的性能,否则您可能不必担心它.

所以直接回答你的问题:我认为可能没有更好的数据类型满足你的需求,因为你建议的那个已经完全没问了.