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)
This question is related to
c++
stl
containers
big-o
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.
Also the STL library reference at http://www.cplusplus.com/reference/stl/ provides the complexity requirements where appropriate.
Another quick lookup table is available at this github page
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
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.
Also the STL library reference at http://www.cplusplus.com/reference/stl/ provides the complexity requirements where appropriate.
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.
Also the STL library reference at http://www.cplusplus.com/reference/stl/ provides the complexity requirements where appropriate.
Another quick lookup table is available at this github page
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
Source: Stackoverflow.com