显然;-)标准容器提供某种形式的保证.
什么类型的保证以及不同类型的容器之间究竟有什么区别？
从工作的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 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)
Nayana Adass.. 65
我找到了很好的资源标准C++容器.可能这就是你们都在寻找的东西.
向量
构造函数
vectorv; Make an empty vector. O(1) vector v(n); Make a vector with N elements. O(n) vector v(n, value); Make a vector with N elements, initialized to value. O(n) vector 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)
有关其他容器,请参阅该页面.
我找到了很好的资源标准C++容器.可能这就是你们都在寻找的东西.
向量
构造函数
vectorv; Make an empty vector. O(1) vector v(n); Make a vector with N elements. O(n) vector v(n, value); Make a vector with N elements, initialized to value. O(n) vector 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)
有关其他容器,请参阅该页面.
我不知道有什么像一张桌子可以让你一目了然地比较所有这些(我不确定这样的桌子是否可行).
当然,ISO标准文档详细列举了复杂性要求,有时在各种相当可读的表中,有时在每个特定方法的可读性较低的要点中.
此外,http: //www.cplusplus.com/reference/stl/上的STL库参考资料还提供了适当的复杂性要求.
京公网安备 11010802040832号 | 京ICP备19059560号-6 