std::vector比普通数组慢很多吗？

Question

我一直以为std::vector是“作为一个数组实现”的普遍认识，但今天我进行了测试，发现事实并非如此：

下面是一些测试结果：

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 可能比几个纳秒慢”这样的评论辩护。

我使用的代码是：

#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;
}

我是做错了什么吗？还是我打破了这个性能神话？

我正在使用Visual Studio 2005的发布模式。

---

在Visual C++中，#define _SECURE_SCL 0可以将UseVector的运行时间减少一半（从8秒降至4秒）。在我看来，这真的非常巨大。

- kizzx2

---

在调试模式下，某些向量版本会添加额外的指令来检查您是否超出数组末尾访问等情况。为了获得真正的时间统计，您必须在发布模式下构建并打开优化选项。 - Martin York

你测量而不是相信网上听到的声明是很好的做法。 - P Shved

"vector"作为一个数组实现，这不仅是"常识"，而是事实。你已经发现了vector是一个通用的可调整大小的数组。恭喜！与所有通用工具一样，可能会出现特殊情况下它并不是最优选择的情况。因此，常规智慧是以vector为起点，必要时再考虑其他替代方案。 - Dennis Zickefoose

笑，把脏碗扔进水槽和把脏碗扔进水槽并检查它们是否破裂的速度差别有多大？ - Imre L

在VC2010中，至少看起来malloc()比resize()更快。从计时中删除内存分配，使用_ITERATOR_DEBUG_LEVEL == 0编译，结果是相同的。 - Andreas Magnusson

Answer 1

使用以下命令:

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

因此，数组比向量快两倍。

但是仔细查看代码后，这是可以预料的；因为您在向量上运行了两次，而数组只运行了一次。注意：当您调整向量大小（resize()）时，不仅会分配内存，还会遍历向量并调用每个成员的构造函数。

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

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

现在再次进行相同的计时：

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

现在向量的性能只比数组略差。在我看来，这种差异微不足道，可能由于与测试无关的许多因素引起。

我还会考虑您未正确初始化/销毁 UseArrray() 方法中的 Pixel 对象，因为构造函数/析构函数都没有被调用（对于这个简单类来说可能没有问题，但任何稍微复杂一些的类（即具有指针或成员具有指针的类）都会导致问题）。

- Martin York

---

你需要使用reserve()而不是resize()。这个函数为对象分配空间（即更改向量的_capacity_），但不创建对象（即_vector的_size_保持不变）。 - James McNellis

您正在执行 10 亿个数组访问操作。时间差为 0.333 秒，即每个数组访问操作的时间差为 0.000000000333 秒。假设您使用的处理器为 2.33 GHz，那么每个数组访问操作需要 0.7 条指令流水线阶段。因此，向量似乎在每个访问操作中使用了额外的一条指令。 - Martin York

难道这不就是我说的吗？我觉得我非常清楚地表达了“reserve”只改变向量的容量而不是大小。 - James McNellis

好的，去理解一下。在向量方法中有很多与异常相关的冗余代码。将/EHsc添加到编译开关中可以清除这些代码，现在assign()实际上比数组更好了。耶。 - Pavel Minaev

在MSVC中，启用异常编译选项会导致明显的性能开销，与是否抛出异常无关。请尝试去掉异常编译选项并进行编译。 - Crashworks

Answer 2

非常好的问题。我来这里时期望找到一些简单的解决方法，可以让向量测试运行更快。但事实并非如此！

优化有所帮助，但仍不够。在进行优化的情况下，使用数组和使用向量之间的性能差异仍然达到2倍。有趣的是，在未进行优化的情况下，使用向量push_back比使用向量本身要快得多。

# g++ -Wall -Wextra -pedantic -o vector vector.cpp
# ./vector
UseArray completed in 20.68 seconds
UseVector completed in 120.509 seconds
UseVectorPushBack completed in 37.654 seconds
The whole thing completed in 178.845 seconds
# g++ -Wall -Wextra -pedantic -O3 -o vector vector.cpp
# ./vector
UseArray completed in 3.09 seconds
UseVector completed in 6.09 seconds
UseVectorPushBack completed in 9.847 seconds
The whole thing completed in 19.028 seconds

想法 #1 - 使用 new[] 替代 malloc

我尝试在 UseArray 函数中将 malloc() 改为 new[]，以便对象可以被构造。并且改变了从单个字段赋值到分配像素实例的方式。哦，还有将内部循环变量重命名为 j。

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

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

        // Same speed as malloc().
        Pixel * pixels = new Pixel[dimension * dimension];

        for(int j = 0 ; j < dimension * dimension; ++j)
            pixels[j] = Pixel(255, 0, 0);

        delete[] pixels;
    }
}

令我惊讶的是，这些更改完全没有任何差异。甚至使用new[]进行更改也一样，它将默认构造所有像素。似乎当使用new[]时，gcc可以优化掉默认构造函数调用，但是当使用vector时却不行。

想法#2-删除重复的operator[]调用

我还试图摆脱三次operator[]查找并缓存对pixels[j]的引用。这实际上使UseVector变慢了！糟糕。

for(int j = 0; j < dimension * dimension; ++j)
{
    // Slower than accessing pixels[j] three times.
    Pixel &pixel = pixels[j];
    pixel.r = 255;
    pixel.g = 0;
    pixel.b = 0;
}

# ./vector 
UseArray completed in 3.226 seconds
UseVector completed in 7.54 seconds
UseVectorPushBack completed in 9.859 seconds
The whole thing completed in 20.626 seconds

想法#3-移除构造函数

将构造函数完全删除怎么样?这样gcc或许可以在创建向量时优化掉所有对象的构建。如果我们将Pixel改为:

struct Pixel
{
    unsigned char r, g, b;
};

结果：快了约10％。仍然比数组慢。嗯。

# ./vector 
UseArray completed in 3.239 seconds
UseVector completed in 5.567 seconds

想法 #4 - 使用迭代器而非循环索引

可以尝试使用一个 vector<Pixel>::iterator 代替循环索引来进行操作。

for (std::vector<Pixel>::iterator j = pixels.begin(); j != pixels.end(); ++j)
{
    j->r = 255;
    j->g = 0;
    j->b = 0;
}

结果：

# ./vector 
UseArray completed in 3.264 seconds
UseVector completed in 5.443 seconds

没有差别，至少不会更慢。我原以为这种性能与#2相似，那里我使用了Pixel&引用。

结论

即使有些聪明的人发现如何使向量循环与数组循环一样快，这也不能说明std::vector的默认行为是好的。编译器并不足够聪明，无法优化掉所有的C++特性，使STL容器像裸数组一样快。

底线是当使用std::vector时，编译器无法优化掉无操作的默认构造函数调用。如果你使用普通的new[]，它可以很好地进行优化。但是使用std::vector就不行了。即使你可以重写代码以消除构造函数调用，这也违反了这里的口号：“编译器比你聪明。STL和纯C一样快。不要担心它。”

- John Kugelman

---

再次感谢您实际运行代码。有时候，当有人试图挑战流行观点时，很容易被无缘无故地抨击。 - kizzx2

"对于编译器来说，想要优化掉所有的C++特性使得STL容器和原始数组一样快，只是一种美好愿望。不错的评论。我有一个理论认为"编译器很聪明"只是一个神话——C++的解析非常困难，编译器只是一个机器。" - kizzx2

我不知道。他确实能够减缓数组测试的速度，但他并没有加速向量测试。我在上面编辑过了，将Pixel的构造函数删除并将其变为一个简单的结构体，但仍然很慢。对于像vector<int>这样使用简单类型的人来说，这是一个坏消息。 - John Kugelman

我真希望我能给你的答案点赞两次。聪明的想法尝试了一下（即使没有一个真正奏效），这些想法我自己都没想到！ - kizzx2

想说明的是，C++的解析非常复杂，但这与优化质量无关。 后者通常发生在将解析结果转换为更低级别表示形式的多个阶段之后。 - Pavel Minaev

Answer 3

这是一个古老但广为流传的问题。

目前，许多程序员将使用C++11。在C++11中，原始码对于UseArray或UseVector的运行速度一样快。

UseVector completed in 3.74482 seconds
UseArray completed in 3.70414 seconds

基本问题在于，当您的 Pixel 结构未初始化时，std::vector<T>::resize( size_t, T const&=T() ) 会使用默认构造的 Pixel 并复制它。编译器没有注意到被要求复制未初始化的数据，因此实际上执行了复制操作。

在 C++11 中，std::vector<T>::resize 有两个重载。第一个是 std::vector<T>::resize(size_t)，另一个是 std::vector<T>::resize(size_t, T const&)。这意味着当您调用 resize 时没有第二个参数，它只是默认构造，并且编译器足够聪明，能够意识到默认构造不做任何事情，所以跳过了对缓冲区的传递。

（添加这两个重载是为了处理可移动、可构造和不可复制的类型——在处理未初始化数据时的性能提升是额外的奖励）。 push_back 解决方案还进行了栅栏检查，这会减慢速度，因此仍然比 malloc 版本慢。

实时例子（我还用chrono::high_resolution_clock替换了计时器）。

请注意，如果您有一个通常需要初始化的结构，但是您希望在扩大缓冲区后处理它，则可以使用自定义的std::vector分配器。 如果您想将其移动到更正常的std::vector中，我认为仔细使用allocator_traits和覆盖==可能会成功，但我不确定。

- Yakk - Adam Nevraumont

---

也很有趣看看 emplace_back 在这里与 push_back 的表现如何。 - Daniel

我无法重现你的结果。编译你的代码clang++ -std=c++11 -O3，UseArray在2.02e-07秒内完成，而UseVector则需要1.3026秒。我还添加了一个UseVectorEmplaceBack版本，它比UseVectorPushBack快大约2.5倍。 - Daniel

@daniel 可能优化器已经从数组版本中删除了所有内容。这是微基准测试的风险。 - Yakk - Adam Nevraumont

没错，我刚才看了一下汇编代码（或者说没有汇编代码）...考虑到这个约6448514倍的差异，我本应该想到的！不知道为什么向量版本不能进行同样的优化..如果用尺寸来构建而不是调整大小，则可以实现这一点。 - Daniel

在该网站上，你是正确的，这些值会显示出来。但是，在Windows clang-cl下使用arch：AVX2最大优化时，UseArray完成于1e-07秒，UseVector完成于1.00729秒，UseVectorPushBack完成于1.4551秒。我怀疑在线编译器必须与其他进程共享CPU，使得任何计时测试无效。我还怀疑当最大优化位于向量无法执行操作时，memcpy会被转换为内置函数。需要查看汇编代码以确保原因。 - rxantos

@rxantos 1e-7 只是意味着编译器发现 UseArray 没有做任何事情，死代码消除了所有内容。1e-7 不是“快”，而是“什么也没做，你只是计时获取时间戳的操作”。 - Yakk - Adam Nevraumont

Answer 4

公正起见，你不能将C++实现与C实现相比，我会称你的malloc版本为C实现。malloc不会创建对象-它只分配原始内存。没有调用构造函数而直接把那块内存当做对象使用是非常糟糕的C++代码（可能是无效的，这点请留给语言专家来解释）。

话虽如此，仅仅将malloc改为new Pixel[dimensions*dimensions]，并将free改为delete [] pixels，对于你拥有的简单Pixel实现来说，并没有多大区别。这是在我的电脑上（E6600, 64-bit）的结果。

UseArray completed in 0.269 seconds
UseVector completed in 1.665 seconds
UseVectorPushBack completed in 7.309 seconds
The whole thing completed in 9.244 seconds

但是稍加改变，情况就会发生逆转：

Pixel.h

（像素头文件）

struct Pixel
{
    Pixel();
    Pixel(unsigned char r, unsigned char g, unsigned char b);

    unsigned char r, g, b;
};

Pixel.cc

#include "Pixel.h"

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

main.cc

#include "Pixel.h"
[rest of test harness without class Pixel]
[UseArray now uses new/delete not malloc/free]

这种方式编译：

$ g++ -O3 -c -o Pixel.o Pixel.cc
$ g++ -O3 -c -o main.o main.cc
$ g++ -o main main.o Pixel.o

我们得到了非常不同的结果：

UseArray completed in 2.78 seconds
UseVector completed in 1.651 seconds
UseVectorPushBack completed in 7.826 seconds
The whole thing completed in 12.258 seconds

使用非内联构造函数Pixel，现在std::vector比原始数组更好。

似乎通过std::vector和std:allocator的分配复杂度太高，无法像简单的new Pixel[n]一样有效地优化。然而，我们可以看到问题仅仅是出在分配上，而不是访问向量。通过调整一些测试函数，将向量/数组创建一次并将其移到循环之外，我们就可以解决这个问题:

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

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

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

并且

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

    int dimension = 999;
    Pixel * pixels = new Pixel[dimension * dimension];

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

我们现在得到以下结果：

UseArray completed in 0.254 seconds
UseVector completed in 0.249 seconds
UseVectorPushBack completed in 7.298 seconds
The whole thing completed in 7.802 seconds

我们可以从中得出的结论是，对于访问而言，std::vector与原始数组相当，但如果需要多次创建和删除向量/数组，则在元素构造函数未内联时，创建复杂对象将比创建简单数组更耗时。我认为这并不令人惊讶。

- camh

---

你仍然有一个内联构造函数——拷贝构造函数。 - Ben Voigt

Answer 5

当我第一次查看您的代码时，这显然不是一个公平的比较；我认为您没有在进行苹果和苹果之间的比较。因此，我想让所有测试都调用构造函数和析构函数； 然后再进行比较。

const size_t dimension = 1000;

void UseArray() {
    TestTimer t("UseArray");
    for(size_t j = 0; j < dimension; ++j) {
        Pixel* pixels = new Pixel[dimension * dimension];
        for(size_t i = 0 ; i < dimension * dimension; ++i) {
            pixels[i].r = 255;
            pixels[i].g = 0;
            pixels[i].b = (unsigned char) (i % 255);
        }
        delete[] pixels;
    }
}

void UseVector() {
    TestTimer t("UseVector");
    for(size_t j = 0; j < dimension; ++j) {
        std::vector<Pixel> pixels(dimension * dimension);
        for(size_t i = 0; i < dimension * dimension; ++i) {
            pixels[i].r = 255;
            pixels[i].g = 0;
            pixels[i].b = (unsigned char) (i % 255);
        }
    }
}

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

    UseArray();
    UseVector();

    return 0;
}

我当时的想法是，通过这种设置，它们应该是完全相同的。但事实证明，我错了。

UseArray completed in 3.06 seconds
UseVector completed in 4.087 seconds
The whole thing completed in 10.14 seconds

那么为什么会出现30%的性能损失呢？STL中所有内容都在头文件中，因此编译器应该能够理解所需的一切。

我认为问题在于循环将所有值初始化为默认构造函数。因此，我进行了一项测试：

class Tester {
public:
    static int count;
    static int count2;
    Tester() { count++; }
    Tester(const Tester&) { count2++; }
};
int Tester::count = 0;
int Tester::count2 = 0;

int main() {
    std::vector<Tester> myvec(300);
    printf("Default Constructed: %i\nCopy Constructed: %i\n", Tester::count, Tester::count2);

    return 0;
}

结果和我预料的一样：

Default Constructed: 1
Copy Constructed: 300

这明显是减速的原因，向量使用复制构造函数从已默认构造的对象初始化元素。

这意味着，在向量构建期间，以下伪操作顺序正在发生：

Pixel pixel;
for (auto i = 0; i < N; ++i) vector[i] = pixel;

由于编译器生成的隐式拷贝构造函数，上述代码被扩展为以下内容：

Pixel pixel;
for (auto i = 0; i < N; ++i) {
    vector[i].r = pixel.r;
    vector[i].g = pixel.g;
    vector[i].b = pixel.b;
}

因此，默认的Pixel保持未初始化状态，而其余的像素则使用默认Pixel的未初始化值进行了初始化。

与使用New[]/Delete[]的替代方案相比：

int main() {
    Tester* myvec = new Tester[300];

    printf("Default Constructed: %i\nCopy Constructed:%i\n", Tester::count, Tester::count2);

    delete[] myvec;

    return 0;
}

Default Constructed: 300
Copy Constructed: 0

它们都保留了它们未初始化的值，并且没有对序列进行双重迭代。

有了这些信息，我们如何测试呢？让我们尝试覆盖隐式复制构造函数。

Pixel(const Pixel&) {}

结果呢？

UseArray completed in 2.617 seconds
UseVector completed in 2.682 seconds
The whole thing completed in 5.301 seconds

总之，如果你经常制作大量的向量，请重新考虑你的算法。无论如何，STL实现并不是因为某种未知原因而变慢，它只是按照你的要求做事情，希望你知道得更好。

- deceleratedcaviar

---

从我们（你、我和其他聪明的人）所拥有的乐趣来看，STL实现的“希望”确实是相当苛刻的:P 基本上，我们可以夸张地得出结论，它希望我已经阅读并分析了它所有的源代码。无论如何:P - kizzx2

太棒了！在 VS 2013 中，这使得向量比数组更快。尽管对于性能关键系统来说，你需要大量测试STL以便能够有效地使用它。 - rozina

请注意，在某些情况下，编译器可以看穿分配并将循环转换为nop: https://godbolt.org/z/sjeaWG5r8 我很好奇为什么我没有看到它对std::vector做同样的事情，但在生产代码中，我不应该有会被丢弃的热循环。 :-D - Ben

Answer 6

尝试使用以下方法：

void UseVectorCtor()
{
    TestTimer t("UseConstructor");

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

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

我使用vector的表现几乎与数组相同。vector的特点是它比数组更加通用，这意味着您必须考虑如何使用它。它可以以许多不同的方式使用，提供甚至数组都没有的功能。如果您将其错误地用于您的目的，就会产生很多开销，但如果使用正确，它通常是一种零开销数据结构。在这种情况下，问题在于您单独初始化了向量（导致所有元素都调用其默认构造函数），然后逐个元素地用正确的值进行覆盖。对于编译器来说，这比使用数组做同样的事情更难优化。这就是为什么vector提供了一个构造函数，让您可以用值X初始化N个元素。当您使用它时，向量的速度与数组一样快。因此，您并没有打破性能神话。但是，您已经表明只有在最佳情况下使用向量才是真正的。这也是一个很好的观点。 :) 光明的一面是，最简单的用法实际上是最快的。如果您将我的代码片段（一行）与John Kugelman的答案进行对比，后者包含大量的调整和优化，仍然无法完全消除性能差异，那么很明显，vector设计得相当巧妙。您不必费尽周折才能获得与数组相等的速度。相反，您必须使用最简单的解决方案。

- jalf

---

我仍然质疑这是否是一个公平的比较。如果你要摆脱内部循环，那么数组等效方法就是构建单个像素对象，然后在整个数组中传输它。 - John Kugelman

使用 new[] 执行与 vector.resize() 相同的默认构造，但速度更快。new[] + 内部循环应该与 vector.resize() + 内部循环具有相同的速度，但实际上它比后者快近一倍。 - John Kugelman

@John：这是一个公平的比较。在原始代码中，数组使用malloc分配，它不初始化或构造任何内容，因此它与我的vector示例一样，实际上是单次遍历算法。至于new[]，显然两者都需要两次遍历，但在new[]情况下，编译器能够优化掉额外的开销，而在vector情况下则无法优化。但我不明白为什么关注次优情况很有趣。如果你关心性能，就不会写那样的代码。 - jalf

@John：有趣的评论。如果我想要跨整个数组进行blit，我猜数组再次是最优解--因为我无法告诉vector::resize()给我一个连续的内存块，而不浪费时间调用无用的构造函数。 - kizzx2

@kizzx2：是和否。在C ++中，数组通常也会被初始化。在C中，您将使用malloc，它不执行初始化，但是在C ++中使用非POD类型时，这不起作用。因此，在一般情况下，C ++数组将是同样糟糕的。也许问题是，如果您经常执行此blitting操作，那么您是否会重用相同的数组/向量？如果您这样做，那么您只需要在最开始支付“无用构造函数”的费用一次。实际的blitting毕竟就像以前一样快。 - jalf

Answer 7

尝试禁用已检查的迭代器并使用发布模式进行构建。这样做不会对性能产生太大影响。

- kloffy

---

尝试使用 #define _SECURE_SCL 0。这使得 UseVector 大约需要 4 秒（与下面的 gcc 相似），但仍然比其慢两倍。 - kizzx2

这几乎可以确定是原因。微软慷慨地默认为我们在调试和发布时都启用了迭代器调试。我们发现这是从2003年升级到2008年后导致巨大减速的根本原因。绝对是Visual Studio中最棘手的陷阱之一。 - Doug T.

@kizzx2 还有另一个可以禁用的宏：HAS_ITERATOR_DEBUGGING 或类似的东西。 - Doug T.

正如@Martin和我的答案所示，即使在-O3优化下，gcc也显示相同的模式。 - John Kugelman

@Doug：看了文档，我认为在发布版本中禁用了“_HAS_ITERATOR_DEBUGGING”：http://msdn.microsoft.com/en-us/library/aa985939(VS.80).aspx - kizzx2

Answer 8

GNU的STL（以及其他STL），给定vector<T>(n)，默认构造一个原型对象T() - 编译器将优化掉空构造函数 - 然后STL的__uninitialized_fill_n_aux会复制在内存地址中保留下来的任何垃圾，并循环填充该对象的副本作为向量中的默认值。所以，“我的”STL并不是循环构造，而是先构造再循环/复制。这是反直觉的，但我应该记得，因为我最近在stackoverflow上评论了关于这一点的问题：对于引用计数对象等，构造/复制可能更有效率。

因此：

vector<T> x(n);

或者

vector<T> x;
x.resize(n);

在许多STL实现中，is_是类似于以下内容的：

T temp;
for (int i = 0; i < n; ++i)
    x[i] = temp;

问题在于当前一代编译器优化器似乎不从temp是未初始化的垃圾的角度出发工作，并且无法优化掉循环和默认复制构造函数调用。你可以合理地争辩说编译器绝对不应该将其优化掉，因为编写上述代码的程序员有一个合理的期望，即即使是垃圾，所有对象在循环后都将是相同的（通常关于“相同”/operator== vs memcmp/operator=等的警告适用）。编译器不能指望有任何额外的洞察std::vector<>的更大上下文或稍后使用数据的情况，以表明这种优化是安全的。

这与更明显、直接的实现形成了对比:

for (int i = 0; i < n; ++i)
    x[i] = T();

我们可以期望编译器对此进行优化。

为了更明确地解释vector行为的合理性，请考虑以下内容：

std::vector<big_reference_counted_object> x(10000);

如果我们创建10000个独立对象和创建10000个引用同一数据，这是一个重大的区别。有人认为，保护C++初学者不会无意中做出如此昂贵的操作的好处，超过了难以优化的复制构造的非常小的实际成本。

原始答案（供参考/理解评论）：没有机会。如果你明智地预留空间，vector和数组的速度是一样快的。...

- Tony Delroy

---

我觉得这个回答完全没有任何用处，对任何人来说都没有一点价值。我希望我可以投两次反对票。 - kizzx2

-1，我的支持就这样流失在kizzx2上了。由于提供的额外功能，向量永远不会像数组一样快，宇宙的规则是，万物都有代价！ - YeenFei

你错过了，托尼...这是一个人工基准测试的例子，但它确实证明了它所声称的。 - Potatoswatter

玫瑰是绿色的，紫罗兰是橙色的，踩票很难受，但答案却在等待着它们。 - Pavel Minaev

Answer 9

Martin York的回答让我不安，因为它似乎是试图掩盖初始化问题。但他是对的，可以确认冗余默认构造函数是性能问题的根源。

[编辑：Martin的答案现在不再建议更改默认构造函数。]

对于眼前的问题，您肯定可以调用vector<Pixel>构造函数的2个参数版本：

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

如果您想使用常量值进行初始化，那么这是有效的，这是一个常见情况。但更一般的问题是：如何高效地使用比常量值更复杂的内容进行初始化？

为此，您可以使用back_insert_iterator，它是一个迭代器适配器。这里有一个使用int向量的示例，尽管对于Pixel同样适用：

#include <iterator>
// Simple functor return a list of squares: 1, 4, 9, 16...
struct squares {
    squares() { i = 0; }
    int operator()() const { ++i; return i * i; }

private:
    int i;
};

...

std::vector<int> v;
v.reserve(someSize);     // To make insertions efficient
std::generate_n(std::back_inserter(v), someSize, squares());

或者你可以使用copy()或transform()代替generate_n()。

缺点是构造初始值的逻辑需要移动到一个单独的类中，这比内部实现不太方便（虽然C++1x中的lambda使这个过程更加美好）。此外，我预计这仍然不会像基于malloc()的非STL版本那样快，但我预计它会接近，因为它只对每个元素进行一次构造。

- j_random_hacker

Answer 10

向量元素还调用像素构造函数。

每个都会导致近一百万个构造函数运行，这是您正在计时的。

编辑：然后有外部1...1000循环，因此进行十亿次构造函数调用！

编辑2：看到UseArray案例的反汇编将是有趣的。由于它除了烧CPU外没有任何效果，优化器可以将整个过程优化掉。

- Graham Perks

---

你说得没错，但问题是：如何关闭这些无意义的构造函数调用呢？对于非 STL 方法来说很容易，但对于 STL 方法来说却很困难/丑陋。 - j_random_hacker