在C++中使用数组或std::vectors，性能差距有多大？

Question

在我们的C++课程中，他们建议不再在新项目中使用C++数组。据我所知，Stroustrup本人也建议不要使用数组。但是，是否存在显著的性能差异呢？

- Tommaso Urli

---

你为什么认为存在性能差距？ - Martin York

通常而言，功能越好，性能就越差。 - tunnuz

我同意关于过早优化的观点，但事先选择更好的存储方法是非常明智的。在现实世界中，通常需要将代码部署并开发下一个产品，优化的步骤往往被忽略。 - Ant

我希望人们不要在某人询问与性能有关的简单问题时大喊“过早优化！”。回答问题，不要过早地假设别人正在做任何过早的事情。 - d7samurai

@d7samaurai：同意，我还没有看到有人尝试使用int main(int argc, const std::vector<string>& argv)。 - Mark K Cowan

Answer 1

在C++中，应避免使用使用new创建的动态数组（即使用动态数组）, 因为你需要跟踪其大小并手动删除它们, 还需要进行各种繁琐的操作。

使用栈上的数组也不建议，因为你没有范围检查，并且传递该数组将丢失关于其大小的任何信息（数组到指针的转换）。这种情况下，应该使用std::array，它将C++数组封装在一个小类中，并提供了size函数和迭代器来遍历它。

现在，std::vector与原生C++数组之间的区别（取自互联网）：

// Comparison of assembly code generated for basic indexing, dereferencing, 
// and increment operations on vectors and arrays/pointers.

// Assembly code was generated by gcc 4.1.0 invoked with  g++ -O3 -S  on a 
// x86_64-suse-linux machine.

#include <vector>

struct S
{
  int padding;

  std::vector<int> v;
  int * p;
  std::vector<int>::iterator i;
};

int pointer_index (S & s) { return s.p[3]; }
  // movq    32(%rdi), %rax
  // movl    12(%rax), %eax
  // ret

int vector_index (S & s) { return s.v[3]; }
  // movq    8(%rdi), %rax
  // movl    12(%rax), %eax
  // ret

// Conclusion: Indexing a vector is the same damn thing as indexing a pointer.

int pointer_deref (S & s) { return *s.p; }
  // movq    32(%rdi), %rax
  // movl    (%rax), %eax
  // ret

int iterator_deref (S & s) { return *s.i; }
  // movq    40(%rdi), %rax
  // movl    (%rax), %eax
  // ret

// Conclusion: Dereferencing a vector iterator is the same damn thing 
// as dereferencing a pointer.

void pointer_increment (S & s) { ++s.p; }
  // addq    $4, 32(%rdi)
  // ret

void iterator_increment (S & s) { ++s.i; }
  // addq    $4, 40(%rdi)
  // ret

// Conclusion: Incrementing a vector iterator is the same damn thing as 
// incrementing a pointer.

注意：如果你使用 new 分配数组，并分配非类对象（如普通的 int）或没有用户定义构造函数的类 并且 不想在初始时初始化元素，则使用 new 分配的数组可能具有性能优势，因为 std::vector 在构造时会将所有元素初始化为默认值（例如 int 为 0）（感谢 @bernie 提醒）。

- litb

---

谁发明了AT&T语法？只要我知道就好了... :) - Mehrdad Afshari

对于Visual C++编译器来说，这并不是真的。但对于GCC编译器来说，却是真的。 - toto

我的回答重点是，向量操作不一定比相应的指针操作慢。当然，它也可能会变慢（如果启用了调试模式，则很容易实现） :) - Johannes Schaub - litb

“索引一个向量和索引一个指针是一回事。”这句话以及其他结论我给加1分。 - Nawaz

@Piotr99 我不会与你争辩，但是在学习更高级语言之后学习汇编语言时，英特尔语法比AT&T语法更加合理，因为AT&T语法具有一些反向的前缀（数字）、后缀（指令）和难以理解的（访问内存）特性。 - Cole Tobin

Answer 2

微优化者前言

记住：

“程序员浪费了大量时间思考或担心程序中非关键部分的速度，而这些效率尝试在考虑调试和维护时实际上会产生强烈的负面影响。我们应该忘记小的效率，大约97％的时间：过早地进行优化是万恶之源。然而，在关键的3％机会中，我们不应该放弃。”

(感谢 metamorphosis 提供完整引用)

不要仅仅因为你认为它更低级别就使用 C 数组而不是 vector（或其他容器）。你会错的。

默认使用 vector（或适合您需求的安全容器），如果您的分析器说它是个问题，请尝试优化它，可以通过使用更好的算法或更改容器来实现。

话虽如此，我们可以回到最初的问题。

静态/动态数组？

C++ 数组类比低级别的 C 数组表现更好，因为它们对自身有很多了解，并且可以回答 C 数组无法回答的问题。它们能够在自己后清理自己。更重要的是，它们通常使用模板和/或内联编写，这意味着在调试中出现大量代码，在发布版本中不会产生任何代码，与其内置的不太安全的竞争没有区别。

总而言之，它分为两类：

动态数组

使用指向malloc或new分配的数组的指针速度最快与std::vector版本相同，并且不太安全（请参见litb's post）。

因此，请使用std::vector。

静态数组

使用静态数组速度最快：

• 与std::array版本一样快
• 但不太安全。

因此，请使用std::array。

未初始化的内存

有时，使用vector而不是原始缓冲区会产生可见的成本，因为vector将在构建时初始化缓冲区，而替换它的代码没有，如bernie在他的answer中所述。

如果是这种情况，则可以通过使用unique_ptr而不是vector来处理它，或者如果该情况在您的代码行中不是异常情况，则实际编写一个类buffer_owner，它将拥有该内存，并为您提供易于使用和安全的访问，包括诸如调整大小（使用realloc？）或其他所需内容的奖励。

- paercebal

---

当你说“使用静态数组最多会和boost :: array 版本一样快”时，这表明你有偏见。 实际上应该是相反的，Boost::array 最多只能像静态数组一样快。 - toto

@toto：这是一个误解：你应该把它理解为“使用静态数组最多只能达到(boost::array版本的速度) && (远不如它安全)”。我会编辑帖子来澄清这一点。顺便说一下，感谢你给予怀疑的好处。 - paercebal

std::array怎么样？ - paulm

始终显示完整引用。“程序员浪费了大量时间思考或担心其程序中非关键部分的速度，而这些对效率的尝试实际上在调试和维护时会产生强烈的负面影响。我们应该忘记小的效率问题，在大约97％的时间内说：过早地优化是万恶之源。但是我们不应该放弃在关键的3％中的机会。”否则它将变成无意义的口号。 - metamorphosis

@bernie：你的情况是一个边缘案例。它可以很容易地解决。使用标准库：只需分配你的缓冲区，将其放入智能指针（例如unique_ptr<char[], FreeDeleter>），然后就完成了。编写自己的类：在相关时使用向量接口，并添加“realloc”功能以供娱乐和乐趣。总的来说，坦白地说，当你在C++中编码时，你很少使用未初始化的缓冲区，有多个非常好的理由。99%的用途可以（并且在可能的情况下）用向量替换而没有任何可见的成本。对于剩下的1%，C++让你定制最佳解决方案。 - paercebal

Answer 3

向量的本质是数组。

性能是相同的。

一个可能导致性能问题的地方是没有正确地给向量分配大小。

当向量被填满时，它将重新调整大小，这会导致新的数组分配，接着大约n个复制构造函数、n个析构函数调用，以及一个数组删除。

如果你的构造/析构比较昂贵，最好一开始就设置向量的正确大小。

有一种简单的方法来演示这一点。创建一个简单的类，展示它何时被构造/销毁/复制/赋值。创建一个这些类的向量，并开始将它们推到向量的后端。当向量被填满时，会出现一系列的活动，因为向量重新调整大小。然后再试一次，将向量大小设置为预期的元素数量。你会看到差异。

- EvilTeach

---

Pedantry: 性能的大O符号相同。std::vector 进行了一些簿记，这可能会花费一些时间。另一方面，当自己实现动态数组时，您最终需要做类似的簿记工作。 - dmckee --- ex-moderator kitten

是的，我明白。他的问题的重点是性能差异是什么...... 我试图解决这个问题。 - EvilTeach

那么gcc的std::vector是否符合标准呢？我相信标准要求vector::push_back具有平均常数复杂度，而在每个push_back上增加容量1将会在考虑到重新分配后导致n^2的复杂度。假设在push_back和insert上采用某种指数级的容量增长方式，则未执行reserve将最多导致向量内容副本的恒定因子增加。如果使用1.5的指数级向量增长因子，则如果未执行reserve()，则需要进行大约3倍的副本操作。 - Yakk - Adam Nevraumont

@bjhend，你错了。标准禁止指数增长：第23.2.3节第16段说：“表101列出了为某些类型的序列容器提供但对其他容器不提供的操作。实现应为“容器”列中显示的所有容器类型提供这些操作，并且应实现它们以便在平摊常数时间内完成。”（表101中包含push_back）。请停止散布恐慌言论。没有主流实现违反这个要求。微软的标准C++库增长因子为1.5x，GCC的增长因子为2x。 - R. Martinho Fernandes

@R.MartinhoFernandes：正是这些增长因素，是我在查看std::vector源代码时希望找到的。我已经做了很长时间了，所以我无法记住细节。等我有时间了，我会重新访问代码的当前版本。 - bjhend

Answer 4

针对Mehrdad的观点做出回应：

然而，在某些情况下，你仍然需要数组。当与低级代码（比如汇编）或要求使用数组的旧库进行交互时，你可能无法使用向量。

这并不完全正确。如果你使用以下语法，向量可以很好地退化为数组/指针：

vector<double> vector;
vector.push_back(42);

double *array = &(*vector.begin());

// pass the array to whatever low-level code you have

这适用于所有主要的STL实现。在下一个标准中，将需要它工作(即使它今天表现得足够好)。

- Frank Krueger

---

标准的原始文本1998年版本确实没有要求，但是2003年的一份附录解决了这个问题，所以它已经被标准覆盖了。http://herbsutter.wordpress.com/2008/04/07/cringe-not-vectors-are-guaranteed-to-be-contiguous/ - Nemanja Trifunovic

C++03 明确表示，只要 n 在数组大小范围内，就可以使用 &v[n] == &v[0] + n 这个表达式。在 C++11 中，包含这个声明的段落并没有改变。 - bjhend

为什么不直接使用std::vector::data()函数？ - paulm

另一方面呢？假如你有一个指针，来自底层代码（或是 C-Export DLL），你将无法在不复制的情况下将其包装成一个向量。 - antipattern

@Manolete：通常情况下，当你需要一个二维数组时，不要使用嵌套的向量或指针数组；如果你有一个平坦的一维 std::vector<double>，你可以将其传递给期望 size_t width, double arr2d[width][] 的 C 接口。当然，在没有可变长度数组（VLA）的 C++ 实现中，第二个参数实际上必须声明为 void* 或 double* 等，只有在 C99 代码中才能看到二维数组，因为你不能将 vec.data() 强制转换为指向可变长度数组的指针。 - Peter Cordes

Answer 5

在C++11中，使用普通数组的理由更少了。

从速度最快到最慢，自然界中有三种类型的数组，取决于它们具有的特性（当然，实现质量可以让列表中的第三种情况非常快）：

1. 静态数组，编译时大小已知。-- std::array<T, N>
2. 动态数组，运行时大小已知且永远不会改变。这里的典型优化是，如果数组可以直接分配在堆栈中，则可以优化。--不可用。也许在C++14之后的C++ TS中有dynarray。在C语言中有可变长度数组
3. 动态可调整大小的数组。-- std::vector<T>

对于1.具有固定元素数的普通静态数组，在C++11中使用std::array<T, N>。

对于2.在运行时指定的固定大小数组，但它们的大小不会发生变化，C++14中存在讨论，但已将其移动到技术规范，并最终从C++14中删除。

对于3.std::vector<T>,通常会在堆上请求内存。虽然这可能会产生性能影响，但您可以使用std::vector<T, MyAlloc<T>>来改善情况，使用自定义分配器。与T mytype[] = new MyType[n];相比的优点是，您可以调整其大小，并且它不会像普通数组一样衰减为指针。

使用提到的标准库类型以避免数组衰减为指针。您将节省调试时间，并且如果使用相同的功能集，则性能与普通数组完全相同。

- Germán Diago

---

在审查了有关n3690的国家机构的评论后，该库组件被从C++14工作草案中投票剔除，并成为一个单独的技术规范。截至n3797版本，这个容器不是C++14草案的一部分。来源：http://en.cppreference.com/w/cpp/container/dynarray - Mohamed ElNakeep

非常好的答案。简洁概括，但比其他任何答案都更详细。 - Mohamed ElNakeep

Answer 6

使用std::vector与使用原始数组时，当您需要一个未初始化的缓冲区（例如，用作memcpy()的目标）时，肯定会对性能产生影响。一个std::vector将使用默认构造函数初始化其所有元素，而原始数组则不会。

关于接受count参数的std:vector构造函数（第三种形式）的C++规范如下所述：

“从各种数据源构造一个新的容器，可选择使用用户提供的分配器alloc。”

3. 使用count个默认插入的T实例构造容器。不进行任何复制。

复杂度

2-3）与count成线性关系

原始数组不会产生这种初始化成本。

请注意，使用自定义分配器可以避免对向量元素进行"初始化"（即使用默认初始化而不是值初始化）。有关更多详细信息，请参阅以下问题：

• 在C++11和Boost.Container下，vector::resize(size_type n)的行为是否正确？
• 如何避免std::vector<>初始化其所有元素？

- bernie

---

但这正是为什么我的small_vector类具有一个resize重载，它默认构造数据，而不像所有常规方法一样值构造。 - Mooing Duck

如果您能更清楚地区分默认构造和值构造，那么这个答案会更好。std::vector将始终进行值构造，在一些边缘情况下可能会有轻微的开销。在您引用的构造函数中，向量进行了值构造，尽管暗示它进行了默认构造，这非常令人恼火。 - Mooing Duck

@MooingDuck 我不会在这里重复已经在许多地方详细解释的内容。然而，我添加了更多信息以显示可以使用自定义分配器来实现默认初始化。 - bernie

Answer 7

选择使用STL。这样做不会影响性能。STL中的算法非常高效，并且可以很好地处理我们大多数人没有考虑到的细节。

- John D. Cook

Answer 8

关于duli的贡献以我的测量为基础。

结论是整数数组比整数向量更快（在我的示例中快了5倍）。但是，对于更复杂/不对齐的数据，数组和向量的速度大致相同。

- lalebarde

Answer 9

STL是一个经过高度优化的库。事实上，甚至建议在需要高性能的游戏中使用STL。数组在日常任务中使用也太容易出错了。今天的编译器也非常聪明，可以用STL真正产生出色的代码。如果您知道自己在做什么，STL通常可以提供必要的性能。例如，通过将向量初始化为所需大小（如果您从一开始就知道），您基本上可以实现数组性能。但是，在与低级代码（即汇编语言）或需要数组的旧库进行交互时，您可能无法使用向量。

- Mehrdad Afshari

---

鉴于向量是连续的，与需要数组的库进行接口仍然相当容易。 - Greg Rogers

是的，但是如果你想要干预向量的内部内容，使用向量的优势会更少。顺便说一下，关键字是“可能不会”。 - Mehrdad Afshari

我只知道一种情况下不能使用向量：如果大小为0。那么&a [0]或&*a.begin()将无法工作。 C++1x将通过引入a.data（）函数来解决这个问题，该函数返回保留元素的内部缓冲区。 - Johannes Schaub - litb

我写下这句话时，脑海中想到的具体情景是基于堆栈的数组。 - Mehrdad Afshari

与C接口的向量或任何连续容器：vec.data()用于数据，vec.size()用于大小。就是这么简单。 - Germán Diago

现在不是这样的。请看迈克·阿克顿（Mike Acton）的演讲《面向数据设计》。 - metamorphosis

Answer 10

如果你以调试模式编译软件，许多编译器将不会内联vector的访问函数。这将使得在性能要求较高的情况下，stl vector实现变得更加缓慢。但它也将使得代码更易于调试，因为你可以在调试器中看到分配了多少内存。

在优化模式下，我期望stl vector的效率接近于数组。这是因为现在许多vector方法都被内联。

- Juan

---

这是很重要的一点。对STL进行分析调试非常慢，这也是人们认为STL很慢的原因之一。 - Erik Aronesty