问题描述

我一直认为 std::vector 被实现为数组"是普遍的智慧，等等等等.今天下楼测试了一下，好像不是这样:

I've always thought it's the general wisdom that std::vector is "implemented as an array," blah blah blah. Today I went down and tested it, and it seems to be not so:

以下是一些测试结果:

UseArray completed in 2.619 seconds
UseVector completed in 9.284 seconds
UseVectorPushBack completed in 14.669 seconds
The whole thing completed in 26.591 seconds

这大约慢了 3 到 4 倍！并不能真正证明vector 可能会慢几纳秒"的评论.

That's about 3 - 4 times slower! Doesn't really justify for the "vector may be slower for a few nanosecs" comments.

以及我使用的代码:

#include <cstdlib>
#include <vector>

#include <iostream>
#include <string>

#include <boost/date_time/posix_time/ptime.hpp>
#include <boost/date_time/microsec_time_clock.hpp>

class TestTimer
{
    public:
        TestTimer(const std::string & name) : name(name),
            start(boost::date_time::microsec_clock<boost::posix_time::ptime>::local_time())
        {
        }

        ~TestTimer()
        {
            using namespace std;
            using namespace boost;

            posix_time::ptime now(date_time::microsec_clock<posix_time::ptime>::local_time());
            posix_time::time_duration d = now - start;

            cout << name << " completed in " << d.total_milliseconds() / 1000.0 <<
                " seconds" << endl;
        }

    private:
        std::string name;
        boost::posix_time::ptime start;
};

struct Pixel
{
    Pixel()
    {
    }

    Pixel(unsigned char r, unsigned char g, unsigned char b) : r(r), g(g), b(b)
    {
    }

    unsigned char r, g, b;
};

void UseVector()
{
    TestTimer t("UseVector");

    for(int i = 0; i < 1000; ++i)
    {
        int dimension = 999;

        std::vector<Pixel> pixels;
        pixels.resize(dimension * dimension);

        for(int i = 0; i < dimension * dimension; ++i)
        {
            pixels[i].r = 255;
            pixels[i].g = 0;
            pixels[i].b = 0;
        }
    }
}

void UseVectorPushBack()
{
    TestTimer t("UseVectorPushBack");

    for(int i = 0; i < 1000; ++i)
    {
        int dimension = 999;

        std::vector<Pixel> pixels;
            pixels.reserve(dimension * dimension);

        for(int i = 0; i < dimension * dimension; ++i)
            pixels.push_back(Pixel(255, 0, 0));
    }
}

void UseArray()
{
    TestTimer t("UseArray");

    for(int i = 0; i < 1000; ++i)
    {
        int dimension = 999;

        Pixel * pixels = (Pixel *)malloc(sizeof(Pixel) * dimension * dimension);

        for(int i = 0 ; i < dimension * dimension; ++i)
        {
            pixels[i].r = 255;
            pixels[i].g = 0;
            pixels[i].b = 0;
        }

        free(pixels);
    }
}

int main()
{
    TestTimer t1("The whole thing");

    UseArray();
    UseVector();
    UseVectorPushBack();

    return 0;
}

是我做错了吗?还是我刚刚打破了这个性能神话?

Am I doing it wrong or something? Or have I just busted this performance myth?

我在 Visual Studio 2005 中使用发布模式.

I'm using Release mode in Visual Studio 2005.

在 Visual C++ 中，#define _SECURE_SCL0 将 UseVector 减少一半(减少到 4 秒).这真的很大，IMO.

In Visual C++, #define _SECURE_SCL 0 reduces UseVector by half (bringing it down to 4 seconds). This is really huge, IMO.

推荐答案

使用如下:

g++ -O3 Time.cpp -I <MyBoost>
./a.out
UseArray 在 2.196 秒内完成
UseVector 在 4.412 秒内完成
UseVectorPushBack 在 8.017 秒内完成
整个事情在 14.626 秒内完成

g++ -O3 Time.cpp -I <MyBoost>
./a.out
UseArray completed in 2.196 seconds
UseVector completed in 4.412 seconds
UseVectorPushBack completed in 8.017 seconds
The whole thing completed in 14.626 seconds

所以数组的速度是向量的两倍.

So array is twice as quick as vector.

但是在更详细地查看代码之后，这是意料之中的；当您两次运行向量并且仅运行一次数组时.注意:当你 resize() 向量时，你不仅在分配内存，而且在向量中运行并调用每个成员的构造函数.

But after looking at the code in more detail this is expected; as you run across the vector twice and the array only once. Note: when you resize() the vector you are not only allocating the memory but also running through the vector and calling the constructor on each member.

稍微重新排列代码，使向量只初始化每个对象一次:

Re-Arranging the code slightly so that the vector only initializes each object once:

 std::vector<Pixel>  pixels(dimensions * dimensions, Pixel(255,0,0));

现在再次做同样的时间:

Now doing the same timing again:

g++ -O3 Time.cpp -I <MyBoost>
./a.out
UseVector 在 2.216 秒内完成

g++ -O3 Time.cpp -I <MyBoost>
./a.out
UseVector completed in 2.216 seconds

向量现在的性能只比数组差一点.IMO 这种差异是微不足道的，可能是由一大堆与测试无关的事情引起的.

The vector now performance only slightly worse than the array. IMO this difference is insignificant and could be caused by a whole bunch of things not associated with the test.

我还要考虑到您没有正确初始化/销毁 UseArrray() 方法中的 Pixel 对象，因为没有调用构造函数/析构函数(这可能不是问题简单的类但稍微复杂一点的类(即带有指针或带有指针的成员)都会导致问题.

I would also take into account that you are not correctly initializing/Destroying the Pixel object in the UseArrray() method as neither constructor/destructor is not called (this may not be an issue for this simple class but anything slightly more complex (ie with pointers or members with pointers) will cause problems.

这篇关于std::vector 比普通数组慢很多吗?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持编程学习网！