Libstdc++ has a "diagnostics" mode that suggests alternate containers
gcc.gnu.org
gcc.gnu.org
http://gcc.gnu.org/onlinedocs/libstdc++/manual/profile_mode....
The work is published under an application called "Perflint". Here's a link to the PDF for the paper:
http://0-portal.acm.org.millennium.lib.cyut.edu.tw/ft_gatewa...
"Abstract—We present perflint, a new industrial strength open source analysis tool that identifies suboptimal use patterns of the C++ standard library. Simply by recompiling and running on a representative input set, programmers receive context sensitive performance advice on their use of standard library data structures and algorithms. Our solution consists of collecting traces of relevant library operations and state during program execution, and then recognizing patterns for which there is a faster alternative, based on a model made of performance guarantees in the C++ language standard and machine knowledge. perflint has already found hundreds of suboptimal patterns in a set of large C++ benchmarks. In one case, following the advice and changing one line of code resulted in 17% program run time reduction."
That way, you could start out with lists when prototyping and building up your app, but under the covers, at runtime, your underlying data structure could swap into something else that optimized your usage pattern. I also think that although this idea sounds fun, that it is premature optimization of the worst kind.
I do think that the idea of Perflint, where you do a little profiling up front as the dev, is much better than trying to use some embedded heuristics. Probably just realizing that its worth doing a little "real world data size" testing makes something Perflint valuable.
[1]: http://ridiculousfish.com/blog/archives/2005/12/23/array/