为什么std::deque的效率如此低？

Question

我想使用std::deque，但是它占用的内存开销似乎过大。我有做错什么吗？

#include "windows.h"
#include "psapi.h"

#include <iostream>
#include <vector>
#include <queue>

int main (int, char* [])
{
    PROCESS_MEMORY_COUNTERS pm;
    GetProcessMemoryInfo(GetCurrentProcess(), &pm, sizeof(pm));
    size_t mem1 = pm.WorkingSetSize;

    std::vector<int> v( 10000000 );

    GetProcessMemoryInfo(GetCurrentProcess(), &pm, sizeof(pm));
    size_t mem2 = pm.WorkingSetSize;

    std::deque<int> q( 10000000 );
    GetProcessMemoryInfo(GetCurrentProcess(), &pm, sizeof(pm));
    size_t mem3 = pm.WorkingSetSize;

    std::cout << mem2 - mem1 << std::endl;
    std::cout << mem3 - mem2 << std::endl;

    return 0;
}

输出结果（在32位Windows系统上）：

40087552
72564736

奖励问题：为什么mem2 - mem1不完全是40000000？

- MarkB

---

你做对了。微软做错了。 - Mooing Duck

@KonradRudolph：嗯，现在微软拥有这个代码了，Dinkumware最初编写了它。deque使用的是16字节的“块”，而GCC使用的是512字节。对于非常小的集合来说，它的开销要少得多。但对于中等或大型集合来说…… - Mooing Duck

@MooingDuck 我知道。 我的意思是，作为一个答案。 - Konrad Rudolph

哦，这很有道理。我认为答案和aschepler的链接已经足够了，我不必停止懒惰。 - Mooing Duck

嗯，Herb Sutter说在大多数情况下，优先使用deque而不是vector（有争议）。但听起来在Windows上使用std::deque并不是一个好主意。 - DavidRR

在他的书《More Exceptional C++》中，Herb Sutter建议使用vector，这本书是后来完成的。 - Phil1970

Answer 1

我认为双端队列不是在连续的内存块中分配的。 从(http://www.cplusplus.com/reference/deque/deque/)： 向量和双端队列都提供非常相似的接口，可以用于类似的目的，但内部工作方式有很大不同：向量使用单个数组，需要偶尔重新分配以进行增长，而双端队列的元素可以分散在不同的存储块中，容器保留必要的信息以在常数时间内提供对其任何元素的直接访问，并具有统一的顺序界面。因此，双端队列在内部比向量稍微复杂，但这使它们能够在某些情况下更有效地增长，特别是在非常长的序列中，在那里重新分配变得更加昂贵。

- Andrew W

Answer 2

正如先前提到的，deque 不是在连续的内存块中分配的。 它必须保留数据以跟踪内存块的位置。 具体细节取决于实现，但可以在STL internals: deque implementation 中找到一些详细信息。

工作集是正在使用的物理内存量。 从working set文档中了解更多信息。

进程的工作集是进程虚拟地址空间中当前驻留在物理内存中的页面集。

很可能已将某些内存换出到磁盘，这会增加不一致性。 mem2 - mem1 之所以不等于40000000，有几个原因。 简单地说，std::vector 对象可能具有其他成员变量。 它可能会跟踪大小变量和开始和结束迭代器。 另一个原因是 Windows 堆还需要跟踪其内存，这需要内存来完成。

从Managing Heap Memory中了解更多信息

实际上，堆管理器需要额外的内存来管理堆中的内存。 因此，它不仅分配所请求的100个字节，还分配一些空间来管理每个特定的内存块。 内存类型和分配大小确定了这种额外内存的大小。

您可以尝试将 std::vector<int> 替换为 int* v = new int[10000000];，您会发现内存差异超过40000000字节。

- Steve

---

实际上，链表不能被使用，因为需要一个具有随机访问迭代器的deque。 - Ben Voigt

@BenVoigt 感谢您的纠正，我已经更正了我的答案。 - Steve

@MooingDuck 这是通过在创建vector之前立即测量mem1，然后直接在之后测量mem2来考虑的。我不认为这两个组件使用的内存在此期间会发生变化。除非我漏掉了什么？ - Steve