显然;-) 标准容器提供了某种形式的保证。
有哪些类型的保证以及不同类型集装箱之间的具体区别是什么?
工作自SGI页面 http://www.sgi.com/tech/stl/ (about STL http://en.wikipedia.org/wiki/Standard_Template_Library)我想出了这个:
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)
我找到了很好的资源标准 C++ 容器 http://www.cs.northwestern.edu/~riesbeck/programming/c++/stl-summary.html。也许这就是你们都在寻找的。
VECTOR
构造函数
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)
其他容器请参考页面。
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)