用于大型向量的节省空间的C++向量分配器？

Question

我正在使用一些C++代码来实现一个图形算法,该算法使用了很多小块内存(gSpan的亲戚,但这并不重要).代码在C++中实现,并使用std :: vectors来存储许多小元素(每个元素大约64个字节).但是,我在比原作者更大的数据集上使用它,而且我的内存不足.

然而,似乎我过早地耗尽了记忆.不成？我怀疑这是因为std :: vectors每次需要更多内存时都会尝试增加大小,并且向量会依赖于连续的内存.我有8GB内存和18GB交换,但是当抛出std :: bad_alloc时,我只使用6.5GB驻留和~8GB虚拟.我抓住了bad_alloc调用并打印出矢量大小,这就是我所看到的:

size: 536870912
capacity: 536870912
maxsize: 1152921504606846975
terminate called after throwing an instance of 'std::bad_alloc'
    what():  std::bad_alloc

所以,显然,我们已达到向量的最大大小,并且库正在尝试分配更多,并且失败.

所以我的问题是:

• 我是否正确认为问题是什么？
• 解决方案是什么(除了"购买更多内存").我愿意交换CPU时间以适应内存.
• 我应该转换整个代码使用std :: list(并以某种方式实现operator []代码使用它的地方吗？)..那甚至会更有效吗？至少它会允许列表元素不连续......对吗？
• 有没有更好的分配器,我可以用来覆盖此用例的向量的标准？
• 我错过了哪些其他解决方案？

由于我不知道最终会使用多少内存,我知道即使我进行了更改,仍然可能没有足够的内存来进行我的计算,但我怀疑我至少可以获得更多的内存然后我就是现在,这似乎很快就放弃了.

Answer 1

我会尝试使用std::deque直接插入vector.有可能因为它(经常)使用一组块,扩展它deque可能比扩展a vector(就所需的额外内存而言)便宜得多.