我该在哪里找到不同STL容器复杂度（性能）的比较？

Question

我花了很长时间在谷歌上搜索，想找到一个比较所有STL容器在插入/推送、删除/弹出等方面复杂性差异的比较。但是我没有找到任何信息，即使在我所有的STL书籍中也没有找到。有什么提示吗？

当然，我知道一些经验法则，但是哪里有明确定义呢？

- RED SOFT ADAIR

---

这里有一个复杂性比较表：http://devmentor.org/references/stl/stl.php - B Faley

我建议不要删除这个问题，因为标题已经足够不同了。 - John Saunders

http://www.cs.northwestern.edu/~riesbeck/programming/c++/stl-summary.html - Smeagol

Answer 1

尝试使用

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

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

来自 complexity.html：

从根本上说，对于实际计算机硬件而非抽象的机器模型，精确定义渐近算法复杂度的概念是困难的。因此，我们采用以下准则： 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被指定用于输入大小m的时间f(m)。F使用操作Gk，在输入大小n上具有指定的运行时间gk(n)。如果在每个Gk比预期慢至多一个因子h(n)的情况下使用F，则F最多会减速h(m)倍。这是因为当前的算法都不会将操作Gk应用于明显大于m的输入。

- Tom

Answer 2

请看这份关于STL、Boost和数组容器性能的报告。

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

- LanDenLabs

Answer 3

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

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

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

我有N. Josuttis的书 C++ Standard Library - Tutorial And Reference 所有这些方面都在那里得到了很好的涵盖。

最好的问候，
Ovanes

- ovanes

---

根据www.cplusplus.com的说法 -“在第三个函数版本中，除非x是不同于*this的列表对象，否则在所有情况下都是常数，此时它在线性范围内（迭代器前进）第一和最后之间。”这似乎意味着长度仍然可以在O(n)时间内实现，因为在您拼接值范围的情况下，拼接可以是线性的（所有其他情况都像简单地将两个大小相加一样简单）。当然，某些实现可能仍然具有O(n) size()用于list。 - Niki Yoshiuchi

是的，这只是一个例子。cplusplus.com是一个不错的网站，但ISO C++标准才是最终答案。cplusplus.com上的信息来自标准（可能是解释或改编），但没有什么比C++标准更明确的了。正如我在上面所述，如果标准没有说明某些内容，那么就由编译器供应商决定，而cplusplus.com也无法提供帮助。我认为特别是在C++的情况下，双重检查可疑的事情非常重要。在标准中找到东西将使您找到更多相关的东西，并大大增强作为C++开发人员的技能。 - ovanes

实际上，我仔细检查了标准，它明确规定了大多数算法和大多数容器访问成员或操作的复杂度。例如：25.3.5.2 set_union [lib.set.union]...
效果：构造两个范围中元素的排序并集;...
要求：结果范围不得与原始范围重叠。
返回：构建范围的末尾。复杂度：最多2 * ((last1 - first1) + (last2 - first2)) - 1次比较。
注：稳定：如果一个元素同时存在于两个范围中，则从第一个范围中复制该元素。 - ovanes