是什么让 STL 如此之快？
如果按照通常实现的方式实现数组类，则与 STL 等价物（如向量）相比，其性能会更慢。那么是什么让 STL 容器/算法变得更快呢？
If one implements an array class the way it is commonly implemented, its performance is slower compared to its STL equivalent like a vector. So what makes STL containers/algorithms fast?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（6）
像
for_each这样的 STL 算法采用可以轻松内联的函数对象。另一方面，C 使用函数指针，这对于编译器来说更难以优化。这在某些算法（例如必须多次调用比较器函数的排序）中产生很大差异。
如果您有兴趣，维基百科有一些更多信息。
编辑：
至于STL的向量类，我认为它不一定比你在glibc中找到的更快。
STL algorithms like
for_eachtake function objects that can be easily inlined. C, on the other hand, uses function pointers which are much more difficult for the compiler to optimize.This makes a big difference in some algorithms like sorting in which the comparer function must be called many times.
Wikipedia has some more information in case you are interested.
EDIT:
As for the STL's vector class, I don't think it's necessarily faster that what you could find in, say, glibc.
大多数人的数组类以恒定增量而不是恒定因子（如标准库要求的那样）增加大小。这意味着插入一个元素大约需要线性时间，而不是标准库的摊余常数时间。
Most people's array classes increase the size by a constant increment rather than a constant factor (as the standard library requires). This means inserting an element takes roughly linear time rather than the amortized constant time for the standard library.
标准库使用良好的算法，就像数组 (std::vector) 的情况一样，每次空间不足时，它通常都会使存储加倍，而简单的实现可能每次都会增加一个元素的存储。由于增加存储量非常缓慢（所有现有数据都需要从旧分配复制到新分配），因此这可能会产生巨大的差异。
类似地，所有其他算法都以相当优化的方式实现。标准库通常不使用任何类型的循环展开或源代码级别的其他此类优化。这只是编译器随后优化的常规良好且简单的代码（具有可怕的变量名称和大量模板）。
我所说的并不是 C++ 标准指定的，而是现有实现中的常见做法。
The standard library uses good algorithms, like in the case of an array (std::vector) it usually doubles the storage every time you run out of space, while a naïve implementation might increment storage by one element every time. Because increasing the amount of storage is very slow (all existing data needs to be copied from the old allocation to the new allocation), this can make a huge difference.
Similarly, all the other algorithms are implemented in rather optimal ways. The standard library usually doesn't use any kind of loop unrolling or other such optimizations on source code level. It is just regular good and simple code (with horrible variable names and a lot of templates) that the compiler then optimizes.
What I said is not specified by the C++ standard, but is what the common practice in existing implementations seems to be.
STL 中的算法已经被各级数学家和计算机科学家研究了多年，他们通常使用绝对最有效的算法，而您的实现可能没有使用这些算法。常见的实现可能不是最快的，但最容易理解； STL 可能正在使用更优化的实现。
The algorithms in the STL have been studied for years by all levels of mathematicians and computer scientists, and they typically use the absolute most efficient algorithms, which your implementation may not be using. The common implementation is one which is probably not fastest, but is easiest to understand; the STL is probably using a more optimized implementation.
除了良好的通用算法（正如其他人所指出的）之外，由于大量使用模板，STL 也非常高效。
模板元程序有一个很好的功能，编译器会积极优化它们。一些编译器对此非常擅长，并将模板缩减为给定任务所需的最小、最有效的代码。一般来说，这意味着尽可能内联函数，并且与特定类型交互的代码被简化为最简单的形式。当然，STL 的大多数实现（以及 Boost 的大多数实现）都充分利用了这一点。
In addition to good, general algorithms (as others have noted), the STL is also quite efficient because of the heavy use of templates.
Template metaprograms have the nice feature that the compiler aggressively optimizes them. Some compilers are very good about this and reduce templates to the smallest, most efficient, required code for a given task. And in general, that means that functions are inlined whenever possible, and code to interact with a particular type is reduced to its simplest form. Most implementations of the STL (and most of Boost), of course, takes advantage of this to the fullest.
代码是以编译器友好的方式编写的，例如内联等。
当然，他们使用的算法是最先进的。
the code is written in a compiler-friendly way, e.g. inlining, etc.
of course, the algorithms they use are state-of-the-art.