c++ - std::vector 在设置大小时性能较低？

Question

今天我想检查在 C++ 中遍历 std::vector 的三种不同方法的性能。结果并没有那么令人惊讶，但还有其他事情引起了我的注意。我注意到，如果我创建一个 vector 并在构造函数中预定义它的大小，有些事情会慢近两倍。请看一下结果:

default constructor...
pushing data...
elapsed: 3.85164s
for ( int i = 0; i < N; i++ ) (*vec)[i]++; - 0.127319s
for ( int i = 0; i < vec->size( ); i++ ) (*vec)[i]++; - 0.128894s
for ( int &n : *vec ) n++; - 0.127325s

vector(N) constructor...
vec.size() is now 500000000
pushing data...
elapsed: 3.93543s
for ( int i = 0; i < N; i++ ) (*vec)[i]++; - 0.126036s
for ( int i = 0; i < vec->size( ); i++ ) (*vec)[i]++; - 0.252865s
for ( int &n : *vec ) n++; - 0.254146s

N 是常量，等于 500000000。 vector 仅包含 int 个随机值 (rand())。每个循环都会递增所有 vector 元素。我正在使用 gettimeofday() POSIX 调用测量时间。

这是完整的源代码:

#include <iostream>
#include <vector>
#include <sys/time.h>

const int N = 500000000;

//For time measurements
static struct timeval t0, t1, tdiff;
static inline void measure_begin( )
{
    gettimeofday( &t0, NULL );
}
static inline double measure_end( )
{
    gettimeofday( &t1, NULL );
    timersub( &t1, &t0, &tdiff );
    return tdiff.tv_sec + tdiff.tv_usec / 1e6;
}


void tests( std::vector<int> *vec )
{
    ///Normal for
    std::cout << "for ( int i = 0; i < N; i++ ) (*vec)[i]++; - ";
    measure_begin( );
    for ( int i = 0; i < N; i++ ) (*vec)[i]++;
    std::cout << measure_end( ) << "s" << std::endl;

    //Normal for, but with size
    std::cout << "for ( int i = 0; i < vec->size( ); i++ ) (*vec)[i]++; - ";
    measure_begin( );
    for ( int i = 0; i < vec->size( ); i++ ) (*vec)[i]++;
    std::cout << measure_end( ) << "s" << std::endl;

    //Ranged for
    std::cout << "for ( int &n : *vec ) n++; - ";
    measure_begin( );
    for ( int &n : *vec ) n++;
    std::cout << measure_end( ) << "s" << std::endl;
}


int main( )
{
    //Create a new vector using the new constructor
    std::cout << "default constructor..." << std::endl;
    std::vector <int> *vec = new std::vector <int>;

    //Data push
    std::cout << "pushing data..." << std::endl;
    measure_begin( );
    for ( int i = 0; i < N; i++ ) vec->push_back( rand( ) ); 
    std::cout << "elapsed: " << measure_end( ) << "s" << std::endl;

    tests( vec );

    //Restart - this time set size in constructor
    delete vec;
    std::cout << "vector(N) constructor..." << std::endl;
    vec = new std::vector <int>;
    vec->reserve( N );
    std::cout << "vec.size() is now " << vec->size( ) << std::endl;

    //Data push
    std::cout << "pushing data..." << std::endl;
    measure_begin( );
    for ( int i = 0; i < N; i++ ) vec->push_back( rand( ) ); 
    std::cout << "elapsed: " << measure_end( ) << "s" << std::endl;

    tests( vec );

    delete vec;

}

我正在使用 GCC 7.30 编译代码，并在 Ubuntu 18.04 上启用了 -O3 标志。

如您所见，使用 std::vector(N) 构造函数，将数据添加到 vector 的速度稍慢，修改它的速度最多可以慢两倍。查看结果，在我看来，在第二种情况下，所有范围方法(vector::begin、vector::end)都花费了更多时间。

我无法解释自己造成这种行为的可能原因。有谁知道发生了什么事吗？

编辑:事实证明，毕竟没有性能问题。正如 Holt 在评论部分首先指出的那样，在第二种情况下，后两个 for 循环迭代默认大小两倍的 vector 。当我使用 vector::reserve 和默认构造函数时，一切似乎都很好。

Answer 1

第一个 vector 添加了 N 个项目。第二个 vector 创建为 N 项，然后将 N 项添加到其中，使其大小增加一倍。