2

Possible Duplicate:
What are the Complexity guarantees of the standard containers?

From the answers to my yesterday's question std::queue<T, list<T> >::size() is slow in O(n)? I learned that my assumptions on STL container performance characteristics are not always right. Time to learn!

Do you know about any "cheat sheet" like overview about common STL (and maybe also Boost) containers like vector, list, deque, map, hash_map/unordered_map etc. regarding the performance characteristics (as indicated by the standard) for operations like insertion, deletion, size() etc.?

Community
  • 1
  • 1
Philipp
  • 11,549
  • 8
  • 66
  • 126
  • 1
    Define here in all there gorie details: http://stackoverflow.com/questions/181693/what-are-the-complexity-guarantees-of-the-standard-containers – Martin York Oct 19 '11 at 07:32

1 Answers1

3

There is a nice chart which compares performances of all standard library containers here.

Alok Save
  • 202,538
  • 53
  • 430
  • 533
  • pretty nice, thanks. However, the performance is not listed for every container (sometimes it just says "depends on container") and sadly the size() operation is said to be O(1) for the adaptors which is not true... – Philipp Oct 19 '11 at 06:58
  • I wish I could paste the relevant content here,but cplusplus.com mentions a copyright,and I am not sure recreating the table here would infringe the copyright or not. – Alok Save Oct 19 '11 at 06:58
  • 1
    Not famous for its accuracy (cplusplus.com). – Martin York Oct 19 '11 at 07:34
  • @LokiAstari: Indeed,I remember the thread here about the same but I do not specifically rememeber anyone citing any incorrectness in the above mentioned table. – Alok Save Oct 19 '11 at 07:36
  • IIRC, part of the problem is that at least C++03 said that `size()` "should" be `O(1)`. Not "is" `O(1)`. This leads to some people thinking that `list::size()` (and in general `size()` for sequences) is guaranteed `O(1)`, when strictly speaking it isn't. One of the `splice()` functions of `list` cannot simultaneously be `O(1)` with `size()`. – Steve Jessop Oct 19 '11 at 10:30