为什么deque在C++中使用比vector更多的RAM？

Question

我有一个问题,我正在努力,我需要使用某种二维数组.数组是固定宽度(四列),但我需要动态创建额外的行.

为此,我一直在使用向量的向量,我一直在使用一些包含这个的嵌套循环:

array.push_back(vector<float>(4));
array[n][0] = a;
array[n][1] = b;
array[n][2] = c;
array[n][3] = d;
n++

添加行及其内容.问题是我似乎因为我试图创建的元素数量而耗尽内存,所以我减少了我使用的数量.但后来我开始阅读deque,并认为它可以让我使用更多的内存,因为它不必是连续的.在这个循环中,我将所有提到的"vector"改为"deque",以及所有声明.但后来看来我再次耗尽内存,这次即使行数减少也是如此.

我查看了我的代码使用了多少内存,当我使用deque时,内存稳定上升到2GB以上,程序很快关闭,即使使用较少的行数.当内存耗尽时,我不确定它在这个循环中的确切位置.

当我使用向量时,即使循环退出,内存使用(对于相同的行数)仍然低于1GB.然后继续进行类似的循环,添加更多行,仍然只达到约1.4GB.

所以我的问题是.对于deque来说,使用两倍以上的向量内存是正常的,还是我在思考我可以在声明/初始化和上面的代码中用"deque"替换单词"vector"时做出错误的假设？

提前致谢.

我正在使用:MS Visual C++ 2010(32位)Windows 7(64位)

Answer 1

这里真正的答案与核心数据结构没什么关系.答案是MSVC对std :: deque的实现特别糟糕,并且退化为指向单个元素的指针数组,而不是它应该是的数组数组.坦率地说,只有两倍的内存使用矢量是令人惊讶的.如果你有更好的deque实现,你会得到更好的结果.

Answer 2

这一切都取决于内部实施deque(我不会谈论,vector因为它相对简单).

事实上,deque有完全不同的保证vector(最重要的是它支持两端插入vectorO(1),而后面只支持O(1)插入).这反过来意味着管理的内部结构deque必须比它更复杂vector.

为此,典型的deque实现将其内存分成几个非连续的块.但是每个单独的存储器块具有固定的开销以允许存储器管理工作(例如,无论块的大小如何,系统可能还需要另外的16或32字节或者其他任何东西,仅用于簿记).因为,与a相反vector,a deque需要许多小的独立块,开销堆叠可以解释你看到的差异.还要注意那些单独的内存块需要管理(可能在不同的结构中？),这可能意味着一些(或很多)额外的开销.

至于解决问题的一种方法,你可以尝试一下@BasileStarynkevitch在评论中提出的建议,这确实会减少你的内存使用量,但它只会到目前为止,因为在某些时候你仍然会耗尽内存.如果你试图在只有256MB RAM的机器上运行你的程序怎么办？任何其他解决方案的目标是减少内存占用,同时仍然试图将所有数据保存在内存中将遇到同样的问题.

处理像您这样的大型数据集时的正确解决方案是调整算法和数据结构,以便能够在整个数据集中处理小分区,并根据需要加载/保存这些分区,以便为其他分区.不幸的是,因为它可能意味着磁盘访问,它也意味着性能大幅下降,但嘿,你不能吃蛋糕也有它.

Answer 3

理论

有效实现双端队列的有两种常用方法:使用修改后的动态数组或使用双向链表.

修改后的动态数组使用的基本上是一个动态数组,可以从两端增长,有时称为数组deques.这些数组deques具有动态数组的所有属性,例如恒定时间随机访问,良好的参考局部性,以及中间的低效插入/移除,并在两端添加了摊销的恒定时间插入/移除,而不是只有一端.

有几种修改动态数组的实现:

1. 从底层数组的中心分配deque内容,并在到达任一端时调整底层数组的大小.这种方法可能需要更频繁的调整并浪费更多空间,特别是当元件仅插入一端时.

2. 将deque内容存储在循环缓冲区中,仅在缓冲区变满时调整大小.这降低了结算的频率.

3. 将内容存储在多个较小的数组中,根据需要在开头或结尾分配其他数组.通过保持包含指向每个较小数组的指针的动态数组来实现索引.

结论

不同的库可以以不同的方式实现deques,但通常作为修改的动态数组.很可能您的标准库使用方法#1来实现std::deque,并且由于您仅从一端附加元素,因此最终会浪费大量空间.出于这个原因,它产生的幻觉std::deque占用了比平时更多的空间std::vector.

此外,如果std::deque将实现为双链表,那将导致浪费空间,因为除了自定义数据之外,每个元素还需要容纳2个指针.

使用方法#3(修改后的动态数组方法)的实现将再次导致浪费空间以容纳额外的元数据,例如指向所有那些小数组的指针.

无论如何,std::deque在存储方面效率低于普通老式std::vector.在不知道您想要实现什么的情况下,我无法自信地建议您需要哪种数据结构.然而,似乎你甚至不知道什么是deques,因此,你真正想要的是你的情况std::vector.一般来说,Deques有不同的应用.