I keep running into this problem all the time. I want to know what the performance guarentee for STL operations are and also it would be nice if they made a quick description regarding what algorithm they used to implement it. Just something simple like: vector.size() -- O(1) performance -- the size of a vector is stored internally and size() simply returns this value With all the time I use going around looking at various references to find this information, I could have just written equivalent code by hand. Right now the best STL documentation I''ve found is at SGI, but they hardly mention anything about performance guarentees. Cheers.

You can use a copy of the C++ Standard, or even a recent draft for complexity guarantees. One online copy of a draft is at
http://www.csci.csusb.edu/dick/c++std/cd2/index.html

Specifically you can refer to
http://www.csci.csusb.edu/dick/c++std/cd2/lib-containers.html
for your vector.size() question.

Awesome. Thanks SiCrane!

Magmai Kai Holmlor - Yup, SGI is always the first site I go to.

My problem is that finding performance guarentees for the STL is pretty much hit and miss. I spend like 30 minutes jumping around to various sites until I find one that has that information.

I just wanted a site that gives a very high level description of how STL operations are actually implemented and the asymptotic performance O(n) thingy, so I have some idea what penalty comes with it.

It helps to know that internally something is implemented in terms of a merge sort or a red-black tree, for instance, because this gives me an idea of other the other lower order terms that get wiped out in asymptotic notation. A certain sort operation might be O(nlog(n)) but I wouldn''t want to use to it on a 20 element array because its implemented as a merge sort. A shell sort would probably be better in this case. 20 elements is small enough that an insertion sort would probably work very well also.

quote:Original post by Z01
I just wanted a site that gives a very high level description of how STL operations are actually implemented and the asymptotic performance O(n) thingy, so I have some idea what penalty comes with it.

It helps to know that internally something is implemented in terms of a merge sort or a red-black tree, for instance, because this gives me an idea of other the other lower order terms that get wiped out in asymptotic notation.

Actually, I don''t know that the implementations are specified by the standard (they might, they might not; I said I don''t know), which would leave implementers free to use whatever techniques are best for their own purposes.

In most cases that the asymptotic notation would matter, though, the operation is external to the container being used (exceptions would include std::list::sort and similar). Therefore, one can implement one''s own algorithms and use them in conjunction with the standard containers and algorithms, providing that balance between readability, flexibility and performance.

Just a thought.