Where can I find a comparison of the different requirements (performance) of STL containers?

Question

I searched Google for a long time to find out a comparison that shows differences in complexity for all STL containers when erasing / deleting an insert / push, etc. I have not found. Also not in all my STL books. Any hint?

Of course, I know some rules of thumb. But where is the definition?

Answer 1

Try

http://www.sgi.com/tech/stl/complexity.html

http://www.sgi.com/tech/stl/table_of_contents.html

From complex.html:

In essence, it is difficult to define the concept of asymptotics as the complexity of the algorithm for real computer equipment, rather than an abstract machine model. Therefore, we are for the following recommendations:

• In order for algorithm A to have running time O (f (n)), there must be a corresponding algorithm A ', which is correct on machines with an arbitrary long pointer and size_t, such that A and A' perform essentially the same sequence of operations on the actual equipment . (In simple cases, A and A 'will be the same. In other cases, A can be simplified by knowing that the addresses are limited.) For inputs of sufficiently large size n, A' should take a maximum time of Cf (n), where C is constant, regardless of n and address size. (Pointer, size_t, and ptrdiff_t assume that operations are constant time, regardless of their size.)
• All container or iterator complexity specifications relate to amortized complexity. Individual surgery may take longer than indicated. But any sufficiently long sequence of operations on the same container or iterator as long as the corresponding amount from the indicated operating costs.
• Algorithms determine either the worst case or the average case of performance and determine which. Unless otherwise indicated, the averages assume that the elements of the container are selected from a finite type with a large number of possible values ​​than the size of the container, and that the elements of the container are independent of each other distribution.
• The complexity specification for the operation f assumes that the operation called f requires no more than a specified execution time. But algorithms, usually called operations, are nothing more than a logarithmic factor slower than those indicated in the expected case.

• If the operations are more expensive than expected by the function F in the current STL, then F will slow down at the most proportionally added value. Any future operations that do not satisfy this property are Explicit.

  To make this accurate, suppose that F is set to use the time f (m) to enter size m. F uses Gk operations, with a given runtime gk (n) on input size n. If F is used in a context in which each Gk is slower than expected by at least factor h (n), then F slows down by no more than a factor h (m). This is because none of the existing algorithms for the operation of Gk on inputs is significantly larger than m.

Answer 2

The ISO C ++ standard defines the complexity of algorithms and methods for accessing containers where necessary. In any other place (unless indicated explicitly), all bets are disabled, and the library developer is free to carry out his own implementation.

For example, you can assume that maps and sets are implemented using red-black trees, but this is not required. Many algorithms are overloaded or specialized for certain categories of iterators (for example, Random Access Iterator), and sometimes they can even be optimized for using special equipment (for example, XMM-register and performing some parallel operations).

Sometimes you really need to logically assume how much the operation may cost due to other requirements, for example, splicing in std :: list should have O (1) complex => length has O (n).

I have a book from N. Josuttis C ++ Standard Library - a textbook and reference book, and all these aspects are well covered there.

Best wishes,
Hovhannes

Answer 3

Take a look at this STL, Boost, and Array performance report.

http://landenlabs.com/code/perf-stl/perf-stl.html