显然;-)标准容器提供了某种形式的保证。
什么类型的保证?不同类型的容器之间到底有什么区别?
在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)
发布于 2008-10-08 08:05:03
我不知道有什么表可以让您一眼就将它们全部比较(我甚至不确定这样的表是否可行)。
当然,ISO标准文档详细地列举了复杂性要求,有时在各种可读性较好的表格中,有时在每个特定方法的可读性较差的要点中。
此外,http://www.cplusplus.com/reference/stl/上的STL库参考在适当的地方提供了复杂性要求。
发布于 2020-05-09 20:14:33
在此github page上提供了另一个快速查找表
注意:这并没有考虑到所有的容器,比如,unordered_map等,但是看起来还是不错的。它只是this的一个更简洁的版本
https://stackoverflow.com/questions/181693
复制相似问题