为什么C++ STL向量在做多个预留时会慢1000倍？

Question

我遇到了一个奇怪的情况.

在我的程序中,我有一个循环,它将一堆数据组合在一个巨大的向量中.我试图找出它运行得如此缓慢的原因,尽管看起来我正在尽一切努力在旅途中以有效的方式分配内存.

在我的程序中,很难确定组合数据的最终向量应该有多大,但是每个数据的大小在处理时都是已知的.因此,我不是一次性保留和调整组合数据向量,而是为每个数据块保留足够的空间,因为它被添加到较大的向量中.那时我遇到了这个问题,可以使用下面的简单片段重复:

std::vector<float> arr1;
std::vector<float> arr2;
std::vector<float> arr3;
std::vector<float> arr4;
int numLoops = 10000;
int numSubloops = 50;

{
    // Test 1
    // Naive test where no pre-allocation occurs

    for (int q = 0; q < numLoops; q++)
    {
        for (int g = 0; g < numSubloops; g++)
        {
            arr1.push_back(q * g);
        }
    }
}

{
    // Test 2
    // Ideal situation where total amount of data is reserved beforehand

    arr2.reserve(numLoops * numSubloops);
    for (int q = 0; q < numLoops; q++)
    {
        for (int g = 0; g < numSubloops; g++)
        {
            arr2.push_back(q * g);
        }
    }
}

{
    // Test 3
    // Total data is not known beforehand, so allocations made for each
    // data chunk as they are processed using 'resize' method

    int arrInx = 0;
    for (int q = 0; q < numLoops; q++)
    {
        arr3.resize(arr3.size() + numSubloops);
        for (int g = 0; g < numSubloops; g++)
        {
            arr3[arrInx++] = q * g;
        }
    }
}

{
    // Test 4
    // Total data is not known beforehand, so allocations are made for each
    // data chunk as they are processed using the 'reserve' method

    for (int q = 0; q < numLoops; q++)
    {
        arr4.reserve(arr4.size() + numSubloops);
        for (int g = 0; g < numSubloops; g++)
        {
            arr4.push_back(q * g);
        }
    }
}

在Visual Studio 2017中编译后,此测试的结果如下:

Test 1: 7 ms
Test 2: 3 ms
Test 3: 4 ms
Test 4: 4000 ms

为什么运行时间存在巨大差异？

为什么要reserve多次调用,然后push_back比调用resize一堆次数长1000 倍,然后进行直接索引访问？

它是如何理解它可能比原始方法(包括根本没有预分配)花费500倍更长的时间？

Answer 1

它是如何理解它可能比原始方法(包括根本没有预分配)花费500倍更长的时间？

这就是你错的地方.您所说的"天真"方法确实会进行预分配.他们只是在幕后完成,很少在电话中完成push_back.每次打电话时,它不仅仅为一个元素分配空间push_back.它分配的数量是当前容量的一个因子(通常在1.5倍和2倍之间).然后在容量用完之前不需要再次分配.这比每次添加50个元素时进行分配的循环更有效,而不考虑当前容量.