标准容器的复杂性保证是什么？

显然;-)标准容器提供了某种forms的保证。

什么types的保证和不同types的容器之间的差异究竟是什么？

从SGI网页 （关于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 Seuqence 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) 

Answer 1

从这里开始： STL复杂性规范 。 然后阅读该网站上的所有容器types，并查看所述的复杂性要求。

希望这可以帮助！

Answer 2

我find了很好的资源标准C ++容器 。 可能这就是你所要找的。

向量

构造函数

 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) 

访问器

 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) 

修饰符

 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) 

对于其他容器，请参阅页面。

Answer 3

标准C ++容器页面提供了STL操作的一个很好的总结。

Answer 4

我不知道有什么东西像一张表，让你一目了然（我不确定这样的表甚至是可行的）。

当然，ISO标准文件详细列举了复杂性要求，有时在各种可读的表格中，其他时间在每个特定方法的可读性较差的点上。

此外， http: //www.cplusplus.com/reference/stl/上的STL库参考在适当的地方提供了复杂性要求。