c++ - 为什么双端队列使用的 RAM 比 C++ 中的 vector 多得多？

Question

我遇到了一个问题，我正在处理需要使用某种二维数组的地方。该数组的宽度是固定的(四列)，但我需要即时创建额外的行。

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

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

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

我查看了我的代码使用了多少内存，当我使用双端队列时，内存稳步上升到 2GB 以上，程序很快就关闭了，即使使用的行数较少也是如此。当内存不足时，我不确定它在这个循环中的确切位置。

当我使用 vector 时，即使在循环退出时，内存使用量(对于相同行数)仍低于 1GB。然后继续进行类似的循环，其中添加了更多行，但仍然只达到大约 1.4GB。

所以我的问题是。双端队列使用的内存是 vector 的两倍以上是正常的，还是我做出了一个错误的假设，认为我可以在声明/初始化和上面的代码中将单词“vector”替换为“deque”？

提前致谢。

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

Answer 1

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