What makes STL fast?

Question

If one implements an array class as it is usually implemented, its performance is slower than its vector equivalent STL equivalent. So what makes STL containers / algorithms fast?

Answer 1

STL algorithms, such as for_each , accept function objects that can be easily embedded. C, on the other hand, uses function pointers, which are much more complicated for the compiler optimizer.

This is important in some algorithms, such as sorting, in which a matching function must be called many times.

Wikipedia has more information if you are interested.

EDIT:

As for the STL vector class, I don't think this is necessarily faster than what you could find, say, glibc.

Answer 2

Most classes of arrays of people increase size using a constant increment rather than a constant factor (as required by the standard library). This means that inserting an element takes approximately linear time, rather than an amortized constant time for the standard library.

Answer 3

The standard library uses good algorithms, for example, in the case of an array (std :: vector) it usually doubles the storage each time you run out of space, and a naive implementation can increase the memory by one element each time. Since the increase in storage is very slow (all existing data must be copied from the old distribution to the new distribution), this can be of great importance.

Similarly, all other algorithms are implemented in fairly optimal ways. The standard library usually does not use any kind of loop reversal or other similar optimizations at the source code level. This is just plain good and simple code (with horrific variable names and lots of patterns) that the compiler then optimizes.

What I said is not specified by the C ++ standard, but this is what seems to be common practice in existing implementations.

Answer 4

Algorithms in STL have been studied for many years by all levels of mathematicians and computer scientists, and they usually use the absolute most efficient algorithms that your implementation cannot use. The general implementation is probably not the fastest, but it is easiest to understand; STL probably uses a more optimized implementation.

Answer 5

the code is written on the compiler, for example, inserts, etc.

Of course, the algorithms they use are the most modern.

Answer 6

In addition to good general algorithms (as others have noted), STL is also quite efficient due to the heavy use of templates.

Template metaplans have a nice feature that the compiler aggressively optimizes. Some compilers are very well versed in this and reduce the templates to the smallest, most efficient, required code for this task. And in general, this means that functions are embedded as much as possible, and the code for interacting with a particular type is reduced to its simplest form. Most STL implementations (and most of Boost), of course, take full advantage of this.