C++ 标准容器的复杂性保证是什么？
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/181693/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
What are the complexity guarantees of the standard containers?
提问by Martin York
Apparently ;-) the standard containers provide some form of guarantees.
显然;-) 标准容器提供了某种形式的保证。
What type of guarantees and what exactly are the differences between the different types of container?
什么类型的保证以及不同类型的容器之间到底有什么区别？
Working from the SGI page(about STL) I have come up with this:
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(n)
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)
采纳答案by Nayana Adassuriya
I found the nice resource Standard C++ Containers. Probably this is what you all looking for.
我找到了不错的资源Standard C++ Containers。大概这就是大家要找的。
VECTOR
向量
Constructors
构造函数
vector<T> v; Make an empty vector. O(1)
vector<T> v(n); Make a vector with N elements. O(n)
vector<T> v(n, value); Make a vector with N elements, initialized to value. O(n)
vector<T> v(begin, end); Make a vector and copy the elements from begin to end. O(n)
Accessors
配件
v[i] Return (or set) the I'th element. O(1)
v.at(i) Return (or set) the I'th element, with bounds checking. O(1)
v.size() Return current number of elements. O(1)
v.empty() Return true if vector is empty. O(1)
v.begin() Return random access iterator to start. O(1)
v.end() Return random access iterator to end. O(1)
v.front() Return the first element. O(1)
v.back() Return the last element. O(1)
v.capacity() Return maximum number of elements. O(1)
Modifiers
修饰符
v.push_back(value) Add value to end. O(1) (amortized)
v.insert(iterator, value) Insert value at the position indexed by iterator. O(n)
v.pop_back() Remove value from end. O(1)
v.assign(begin, end) Clear the container and copy in the elements from begin to end. O(n)
v.erase(iterator) Erase value indexed by iterator. O(n)
v.erase(begin, end) Erase the elements from begin to end. O(n)
For other containers, refer to the page.
对于其他容器，请参阅页面。
回答by Michael Burr
I'm not aware of anything like a single table that lets you compare all of them in at one glance (I'm not sure such a table would even be feasible).
我不知道有什么东西可以让你一眼比较所有的表（我不确定这样的表是否可行）。
Of course the ISO standard document enumerates the complexity requirements in detail, sometimes in various rather readable tables, other times in less readable bullet points for each specific method.
当然，ISO 标准文档详细列举了复杂性要求，有时以各种可读性很强的表格形式列出，有时以每种特定方法的可读性较差的要点列出。
Also the STL library reference at http://www.cplusplus.com/reference/stl/provides the complexity requirements where appropriate.
此外，http://www.cplusplus.com/reference/stl/ 上的 STL 库参考提供了适当的复杂性要求。
回答by whiteknight
Another quick lookup table is available at this github page
另一个快速查找表可在此github 页面上找到
Note : This does not consider all the containers such as, unordered_map etc. but is still great to look at. It is just a cleaner version of this
注意：这不考虑所有容器，例如 unordered_map 等，但仍然很好看。这仅仅是一个更清洁的版本，这
