c++ - 如果我想要最大速度，我应该只在 std::vector 上使用数组吗？

Question

就目前而言，这个问题不适合我们的问答形式。我们希望答案得到事实、引用或专业知识的支持，但这个问题可能会引起辩论、争论、投票或扩展讨论。如果您觉得这个问题可以改进并可能重新打开，visit the help center为指导。




8年前关闭。




我正在编写一些需要尽可能快的代码，而不会占用我所有的研究时间(换句话说，没有手动优化的程序集)。

我的系统主要由一堆 3D 点(原子系统)组成，因此我编写的代码进行了大量距离比较、最近邻搜索以及其他类型的排序和比较。这些是大型的、百万或十亿点系统，并且简单的 O(n^2) 嵌套 for 循环不会削减它。

对我来说最简单的方法是使用 std::vector保持点坐标。起初我认为它可能与数组一样快，所以太棒了!然而，这个问题(Is std::vector so much slower than plain arrays?)却让我有一种很不安的感觉。我没有时间使用数组和 vector 编写所有代码并对它们进行基准测试，因此我现在需要做出正确的决定。

相信有人知道std::vector背后的详细实现可以以很少的速度损失使用这些功能。但是，我主要用 C 编程，所以我不知道是什么 std::vector正在幕后做，我不知道 push_back每次我调用它时都会执行一些新的内存分配，或者我可能陷入的其他“陷阱”使我的代码非常慢。

不过数组很简单；我确切地知道什么时候分配内存，我所有算法的顺序是什么，等等。没有我可能不得不忍受的黑盒未知数。然而，我经常看到人们批评在互联网上使用数组而不是 vector ，我不禁怀疑我是否遗漏了更多信息。

编辑 :澄清一下，有人问“你为什么要用数组或 vector 来操作这么大的数据集”？好吧，最终一切都存储在内存中，因此您需要选择一些底层抽象。例如，我使用 kd-trees 来保存 3D 点，但即便如此，kd-tree 也需要基于数组或 vector 构建。

此外，我并不是在暗示编译器不能优化(我知道最好的编译器在很多情况下都可以胜过人类)，只是说它们不能优化得比它们的约束所允许的更好，而且我可能只是由于我的无知而无意中引入了约束 vector 的实现。

Answer 1

一切都取决于您如何实现算法。 std::vector是这样一个通用的容器概念，它给了我们灵活性，但让我们有自由和责任来故意构建算法的实现。我们将从 std::vector 观察到的大部分效率开销来自 复印 . std::vector提供了一个构造函数，它允许你用值 X 初始化 N 个元素，当你使用它时， vector 和数组一样快。
我做了一个测试 std::vector与描述的数组 here ,

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

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

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

    return 0;
}

这是结果(在 Ubuntu amd64 上用 g++ -O3 编译):

UseArray completed in 0.325 seconds
UseVector completed in 1.23 seconds
UseConstructor completed in 0.866 seconds
UseVectorPushBack completed in 8.987 seconds
The whole thing completed in 11.411 seconds

清楚 push_back在这里不是好的选择，使用构造函数仍然比数组慢 2 倍。
现在，为 Pixel 提供空的拷贝:

Pixel(const Pixel&) {}

给我们以下结果:

UseArray completed in 0.331 seconds
UseVector completed in 0.306 seconds
UseConstructor completed in 0 seconds
UseVectorPushBack completed in 2.714 seconds
The whole thing completed in 3.352 seconds

所以总而言之:重新考虑你的算法，否则，也许会求助于 New[]/Delete[] 周围的自定义包装器。无论如何，由于某些未知原因，STL 实现并不会变慢，它只是完全按照您的要求执行；希望你知道得更好。
如果您刚开始使用 vector ，它们的行为可能会令人惊讶，例如以下代码:

class U{
    int i_;
public:
    U(){}
    U(int i) : i_(i) {cout << "consting " << i_ << endl;}
    U(const U& ot) : i_(ot.i_) {cout << "copying " << i_ << endl;}
};

int main(int argc, char** argv)
{   
    std::vector<U> arr(2,U(3));
    arr.resize(4);
    return 0;
}

结果为:

consting 3

copying 3

copying 3

copying 548789016

copying 548789016

copying 3

copying 3