为什么 deque 在 C++ 中使用的 RAM 比 vector 多得多? [英] Why is deque using so much more RAM than vector in C++?

问题描述

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

I have a problem I am working on where I need to use some sort of 2 dimensional array. The array is fixed width (four columns), but I need to create extra rows on the fly.

为此，我一直在使用向量的向量，并且我一直在使用一些包含此内容的嵌套循环:

To do this, I have been using vectors of vectors, and I have been using some nested loops that contain this:

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"，以及所有声明.但后来似乎我再次耗尽内存，这一次即使减少行数.

to add the rows and their contents. The trouble is that I appear to be running out of memory with the number of elements I was trying to create, so I reduced the number that I was using. But then I started reading about deque, and thought it would allow me to use more memory because it doesn't have to be contiguous. I changed all mentions of "vector" to "deque", in this loop, as well as all declarations. But then it appeared that I ran out of memory again, this time with even with the reduced number of rows.

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

I looked at how much memory my code is using, and when I am using deque, the memory rises steadily to above 2GB, and the program closes soon after, even when using the smaller number of rows. I'm not sure exactly where in this loop it is when it runs out of memory.

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

When I use vectors, the memory usage (for the same number of rows) is still under 1GB, even when the loop exits. It then goes on to a similar loop where more rows are added, still only reaching about 1.4GB.

所以我的问题是.deque 使用向量内存的两倍以上是正常的，还是我做出了错误的假设，认为我可以在声明/初始化和上述代码中将向量"替换为deque"?

So my question is. Is this normal for deque to use more than twice the memory of vector, or am I making an erroneous assumption in thinking I can just replace the word "vector" with "deque" in the declarations/initializations and the above code?

提前致谢.

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

I'm using: MS Visual C++ 2010 (32-bit) Windows 7 (64-bit)

推荐答案

这完全取决于 deque 的内部实现(我不会谈论 vector 因为它比较直接).

It all depends on the internal implementation of deque (I won't speak about vector since it is relatively straightforward).

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

Fact is, deque has completely different guarantees than vector (the most important one being that it supports O(1) insertion at both ends while vector only supports O(1) insertion at the back). This in turn means the internal structures managed by deque have to be more complex than vector.

为此，典型的 deque 实现会将其内存拆分为几个不连续的块.但是每个单独的内存块都有固定的开销以允许内存管理工作(例如，无论块的大小如何，系统可能需要另外 16 或 32 字节或其他任何内容，仅用于簿记).由于与 vector 不同，deque 需要许多小的、独立的块，因此开销会堆积起来，这可以解释您看到的差异.另请注意，需要管理这些单独的内存块(可能在单独的结构中?)，这可能也意味着一些(或很多)额外的开销.

To allow that, a typical deque implementation will split its memory in several non-contiguous blocks. But each individual memory block has a fixed overhead to allow the memory management to work (eg. whatever the size of the block, the system may need another 16 or 32 bytes or whatever in addition, just for bookkeeping). Since, contrary to a vector, a deque requires many small, independent blocks, the overhead stacks up which can explain the difference you see. Also note that those individual memory blocks need to be managed (maybe in separate structures?), which probably means some (or a lot of) additional overhead too.

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

As for a way to solve your problem, you could try what @BasileStarynkevitch suggested in the comments, this will indeed reduce your memory usage but it will get you only so far because at some point you'll still run out of memory. And what if you try to run your program on a machine that only has 256MB RAM? Any other solution which goal is to reduce your memory footprint while still trying to keep all your data in memory will suffer from the same problems.

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

A proper solution when handling large datasets like yours would be to adapt your algorithms and data structures in order to be able to handle small partitions at a time of your whole dataset, and load/save those partitions as needed in order to make room for the other partitions. Unfortunately since it probably means disk access, it also means a big drop in performance but hey, you can't eat the cake and have it too.

这篇关于为什么 deque 在 C++ 中使用的 RAM 比 vector 多得多?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！