1

我正在尝试收集大量随机数来进行算法分析。然后我遇到了这个我无法解释的问题。考虑以下代码：

#include <exception>
#include <iostream>
#include <deque>

typedef unsigned long long mytype;

const mytype SIZE = 150000000;

int main()
{
    std::deque<mytype> rand;

    try 
    {
        for (mytype i = 0; i< SIZE; i++)
        {
            rand.push_back(1); //Just push a dummy number into the deque
        }

    }
    catch (std::exception& e)
    {
        {
           std::cout << e.what() << std::endl;
        }
    }

    return 0;
}

这将导致错误的分配异常。问题是如果我使用 vector 和 reserve() 它将起作用。如果我没有正确理解，请纠正我，deque 不是那种容量更大的数据结构，因为它不像向量那样连续分配内存吗？

我在 Win8 x64、Visual Studio 2012、带有 8G RAM 的英特尔 i7 上运行它。感谢您分享您的想法

4

1 回答 1

2

该问题是由内存碎片引起的。

如果直接使用vector.reserve，一开始你会得到一大块内存。应用程序启动时内存碎片较低，因此此时分配巨大内存的机会很高。

当你在循环中使用 deque.push_back 时，deque 将首先保留一小块内存（例如大小为 A 字节），随着循环运行，deque 达到其内存限制，然后它会分配 2*A字节，然后将数据复制到新内存中；然后是 4*A 字节，然后是 8*A 字节....我很久以前读过 deque 的代码，所以细节可能有问题，这里的想法是这个循环会导致大量内存分配/释放，这会导致高内存碎片，如果内存碎片高，分配巨大内存的机会就低。

有关内存碎片的详细信息，请参阅此。

于 2013-02-21T09:25:01.190 回答