C++ 我在哪里可以找到不同 STL 容器复杂性（性能）的比较？

Where do I find a comparison of different STL containers complexity (performance)?

提问by RED SOFT ADAIR

I googled quite a while in order to find out a comparison that shows the differences in complexity for all STL-Containers on insert/push erase/pop etc. I did not find any. Also not in all of my STL Books. Any hint?

我在谷歌上搜索了一段时间，以找出一个比较，该比较显示了所有 STL 容器在插入/推送擦除/弹出等方面的复杂性差异。我没有找到任何。也不是在我所有的 STL 书籍中。任何提示？

I know some rules of thumb of course. But where is a definition?

我当然知道一些经验法则。但定义在哪里？

回答by Tom

Try with

试试

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

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

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

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

From complexity.html:

从complexity.html：

Fundamentally, it is difficult to define the notion of asymptotic algorithm complexity precisely for real computer hardware instead of an abstract machine model. Thus we settle for the following guidelines:

1. For an algorithm A to have running time O(f(n)), there must be a corresponding algorithm A' that is correct on machines with arbitrarily long pointer and size_t types, such that A and A' perform essentially the same sequence of operations on the actual hardware. (In simple cases A and A' will be the same. In other cases A may have been simplified with the knowledge that adresses are bounded.) For inputs of sufficiently large size n, A' must take at most time Cf(n), where C is a constant, independent of both n and the address size. (Pointer, size_t, and ptrdiff_t operations are presumed to take constant time independent of their size.)
2. All container or iterator complexity specifications refer to amortized complexity. An individual operation may take longer than specified. But any sufficiently long sequence of operations on the same container or iterator will take at most as long as the corresponding sum of the specified operation costs.
3. Algorithms specify either worst-case or average case performance, and identify which. Unless otherwise stated, averages assume that container elements are chosen from a finite type with more possible values than the size of the container, and that container elements are independently uniformly distributed.
4. A complexity specification for an operation f assumes that operations invoked by f require at most the specified runtime. But algorithms generally remain appropriate if the invoked operations are no more than a logarithmic factor slower than specified in the expected case.

5. If operations are more expensive than assumed by a function F in the current STL, then F will slow down at most in proportion to the added cost. Any future operations that fail to satisfy this property will make that explicit.

   To make this precise, assume F is specified to use time f(m) for input of size m. F uses operations Gk, with specified running times gk(n) on input size n. If F is used in a context in which each Gk is slower than expected by at most a factor h(n), then F slows down by at most a factor h(m). This holds because none of the current algorithms ever apply the operations Gk to inputs significantly larger than m.

从根本上说，很难为真实的计算机硬件而不是抽象的机器模型精确定义渐近算法复杂度的概念。因此，我们满足以下准则：

1. 对于具有运行时间 O(f(n)) 的算法 A，必须有相应的算法 A' 在具有任意长指针和 size_t 类型的机器上是正确的，使得 A 和 A' 执行基本相同的操作序列在实际硬件上。（在简单的情况下，A 和 A' 将相同。在其他情况下，A 可能已经通过知道地址有界的知识进行了简化。）对于足够大的大小 n 的输入，A' 必须最多花费时间 Cf(n)，其中 C 是一个常数，与 n 和地址大小无关。（假定指针、size_t 和 ptrdiff_t 操作花费恒定的时间，而与其大小无关。）
2. 所有容器或迭代器复杂度规范均指摊销复杂度。单个操作可能需要比指定的更长的时间。但是在同一个容器或迭代器上的任何足够长的操作序列最多需要指定操作成本的相应总和。
3. 算法指定最坏情况或平均情况的性能，并确定哪个。除非另有说明，平均值假设容器元素是从有限类型中选择的，其可能值多于容器的大小，并且容器元素是独立均匀分布的。
4. 操作 f 的复杂性规范假定 f 调用的操作至多需要指定的运行时间。但是，如果调用的操作不超过预期情况下指定的对数因子，则算法通常仍然适用。

5. 如果操作比当前 STL 中的函数 F 假设的更昂贵，那么 F 将最多与增加的成本成比例地减慢。任何无法满足此属性的未来操作都将使其明确。

   为了精确起见，假设 F 被指定为使用时间 f(m) 输入大小为 m。F 使用操作 Gk，在输入大小 n 上指定运行时间 gk(n)。如果在每个 Gk 比预期慢最多一个因子 h(n) 的上下文中使用 F，则 F 最多减慢一个因子 h(m)。这是成立的，因为当前的算法都没有将操作 Gk 应用于明显大于 m 的输入。

回答by ovanes

ISO C++ Standard defines the complexity of algorithms and container access methods, where required. Anywhere else (if not explicitly stated) all bets are off and a library implementor is free to do their own implementation.

ISO C++ 标准在需要时定义了算法和容器访问方法的复杂性。在其他任何地方（如果没有明确说明），所有赌注都已关闭，库实现者可以自由地进行自己的实现。

For example you can assume that maps and sets are implemented using red-black trees, but there is no requirement to do so. Many algorithms are overloaded or specialized for particular iterator categories (like Random Access Iterator) and sometimes might be even optimized to perform from special hardware (like XMM register and execute some some operations in parallel).

例如，您可以假设地图和集合是使用红黑树实现的，但没有要求这样做。许多算法被重载或专门用于特定的迭代器类别（如随机访问迭代器），有时甚至可能被优化以从特殊硬件执行（如 XMM 寄存器并并行执行某些操作）。

Sometimes you really have to logically assume how much an operation might cost, due to other requirements, like splice in std::list must have O(1) complexity => length has O(n).

有时你真的必须在逻辑上假设一个操作可能花费多少，由于其他要求，比如 std::list 中的 splice 必须有 O(1) 复杂度 => 长度有 O(n)。

I have the book from N. Josuttis C++ Standard Library - Tutorial And Referenceand all these aspects are well covered there.

我有一本来自 N. Josuttis C++ Standard Library - Tutorial And Reference 的书，所有这些方面都在那里得到了很好的介绍。

Best Regards,
Ovanes

最好的问候，
Ovanes

回答by LanDenLabs

Take a look at this report on STL, Boost and array container performance

看看这份关于 STL、Boost 和阵列容器性能的报告

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

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