STL为什么快？

Question

如果按照常规方式实现一个数组类，其性能与STL等效的向量相比要慢。那么是什么让STL容器/算法更快呢？

- jasonline

---

“常规实现方式”这个说法非常模糊，每个人都会按照自己的方式去实现。从技术上来说，通常并没有“实现”，而是被“复用”。 - Mehrdad Afshari

请指明您所指的操作，并说明您是如何确定标准库更快的。 - Malte Clasen

@Mehrdad, Malte：是的，我同意。但是假设对于一个数组类，在中间插入一个元素需要将元素向后移动一位来创建一个空位置以容纳新元素。这种实现比vector的push_back()慢得多。我通过获取时间或时钟周期来确定它。 - jasonline

你正在将向数组中插入元素与vector.push_back()进行比较吗？那不是在插入，而是在追加。 - UncleBens

@Malte-Clasen：@UncleBens：没错。看起来他在比较苹果和橙子。 - Mike Dunlavey

@UncleBens，Malte：哎呀，抱歉我的错误。我是指insert()而不是push_back()。是的，我同意push_back()是用于追加的。 - jasonline

Answer 1

STL算法比如for_each采用函数对象，这些函数对象可以很容易地内联。相反，C语言使用函数指针，这对编译器的优化来说要困难得多。

这在某些算法中会产生很大的差异，例如排序算法中，比较函数必须被调用多次。

如果您感兴趣，维基百科在这里提供了更多信息。

编辑：

至于STL的vector类，我认为它不一定比你在glibc中找到的更快。

- Manuel

---

那可能是其中一个关键点:D - Hassan Syed

Answer 2

大多数人的数组类增加大小是通过常量增量而不是常量因子（标准库所需）来实现的。这意味着插入一个元素需要大约线性时间，而不是标准库的摊销常量时间。

- Jerry Coffin

---

任何做这件事的开发者都应该归还他的计算机科学学位。 - Tamas Czinege

您假设开发者拥有计算机科学学位 :) +1 - Billy ONeal

Answer 3

标准库使用了优秀的算法，例如在数组（std::vector）的情况下，它通常会在空间不足时将存储空间翻倍，而天真的实现可能每次只增加一个元素的存储空间。由于增加存储空间非常缓慢（所有现有数据都需要从旧分配复制到新分配），这可能会产生巨大的差异。

同样，所有其他算法都以相当优化的方式实现。标准库通常不在源代码级别上使用任何循环展开或其他此类优化。它只是普通的好的和简单的代码（带有可怕的变量名和大量的模板），然后编译器进行优化。

我所说的并没有被C++标准规定，但这是现有实现中的通行做法。

- Tronic

---

当容量达到一兆字节左右时，将存储器翻倍实际上可能会带来不小的负面影响... - Hassan Syed

Hassan Syed：你从未浪费超过分配内存的50％。我不会说那是“相当糟糕”的。 - Tamas Czinege

显然，std::vector的增长因子为1.5：http://amitp.blogspot.com/2003_11_01_amitp_archive.html#106843046050898865 - Manuel

@Manuel：这必须是一个常数因子。虽然在大多数早期实现中使用了2，但现在1.5（左右）更为普遍。据我所知，安德鲁·科尼希是第一个指出为什么应该这样做的人：http://groups.google.com/group/comp.lang.c++.moderated/msg/ba558b4924758e2e - Jerry Coffin

@Jerry - 感谢提供链接，了解1.5为何被广泛使用的原因很好（我认为Python列表也是这样增长的）。但你似乎在暗示我说它不是一个恒定因素，是什么让你这么想呢？ - Manuel

Answer 4

STL中的算法已经被各级数学家和计算机科学家研究了多年，它们通常使用绝对最有效的算法，而您的实现可能没有使用。常见的实现可能不是最快的，但最容易理解；STL可能正在使用更优化的实现。

- Ricket

---

当所有种类的高素质人批准了某事（如果他们批准了），不要认为你不需要思考。他们也有可能是错误的。 - Mike Dunlavey

-1：我认为这根本不是真实的陈述。 "算法" 是特定于实现的。只有 STL 算法/容器等的公开行为是指定的。有许多许多 STL 的实现，它们并没有全部接受审查（事实上，我会说大多数都没有），远远没有达到你所声称的水平。许多实现比普通程序员编写的更好，但一个好的程序员可以轻松地与它们竞争... - user123456

Answer 5

除了好的通用算法（正如其他人所指出的），STL由于大量使用模板而非常高效。

模板元编程具有一个很好的特性，即编译器会积极地对它们进行优化。一些编译器在这方面非常擅长，可以将模板缩小到最小、最有效、最需要的代码来完成给定的任务。一般来说，这意味着函数在可能的情况下被内联，并且与特定类型交互的代码被简化到其最简形式。当然，STL的大多数实现（以及大多数Boost库）都充分利用了这一点。

- greyfade

Answer 6

代码以编译器友好的方式编写，例如内联等。

当然，他们使用的算法是最先进的。

- Yin Zhu