标准容器的复杂性保证是什么？
标准容器的复杂性保证是什么？
提问于 2008-10-08 07:35:11
显然;-)标准容器提供了某种形式的保证。
什么类型的保证?不同类型的容器之间到底有什么区别？
在the SGI page (关于STL)的工作中，我得出了以下结论：
Container Types:
================
Container:
Forward Container
Reverse Container
Random Access Container
Sequence
Front Insert Sequence
Back Insert Sequence
Associative Container
Simple Associative Container
Pair Associative Container
Sorted Associative Container
Multiple Associative Container
Container Types mapped to Standard Containers
=============================================
std::vector: Sequence Back Sequence Forward/Reverse/Random Container
std::deque: Sequence Front/Back Sequence Forward/Reverse/Random Container
std::list: Sequence Front/Back Sequence Forward/Reverse Container
std::set: Sorted/Simple/Unique Associative Container Forward Container
std::map: Sorted/Pair/Unique Associative Container Forward Container
std::multiset: Sorted/Simple/Multiple Associative Container Forward Container
std::multimap: Sorted/Pair/Multiple Associative Container Forward Container
Container Guarantees:
=====================
Simp
or
For Rev Rand Front Back Assoc Sort Mult
Cont: Cont: Cont Cont: Sequ: Sequ: Sequ: Cont: Cont: Cont:
Copy Const: O(n)
Fill Const: O(n)
begin() O(1)
end() O(1)
rbegin() O(1)
rend() O(1)
front() O(1)
push_front() O(1)
pop_front() O(1)
push_back() O(1)
pop_back() O(1)
Insert() O(ln(n))
Insert: fill O(n)
Insert: range O(n) O(kln(n)+n)
size() O(1)
swap() O(1)
erase key O(ln(n))
erase element O(1)
erase range O(ln(n)+S)
count() O(log(n)+k)
find() O(ln(n))
equal range O(ln(n))
Lower Bound/Upper Bound O(ln(n))
Equality O(n)
InEquality O(n)
Element Access O(1)回答 2
Stack Overflow用户
发布于 2008-10-08 08:05:03
我不知道有什么表可以让您一眼就将它们全部比较(我甚至不确定这样的表是否可行)。
当然，ISO标准文档详细地列举了复杂性要求，有时在各种可读性较好的表格中，有时在每个特定方法的可读性较差的要点中。
此外，http://www.cplusplus.com/reference/stl/上的STL库参考在适当的地方提供了复杂性要求。
Stack Overflow用户
发布于 2020-05-09 20:14:33
在此github page上提供了另一个快速查找表
注意:这并没有考虑到所有的容器，比如，unordered_map等，但是看起来还是不错的。它只是this的一个更简洁的版本
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/181693
复制相关文章
相似问题