Prev Up
Go backward to Semantics
Go up to Formalization

Performance

Project: Formalize the performance requirements of STL

[Musser] In the case of performance requirements, a degree of precision is achieved in the ANSI/ISO C++ Standard and the SGI STL concept web through the use of big-O bounds and bounds on operation counts (although there are several errors in stating bounds on operation counts in the Standard, resulting in unachievable requirements). Overall, more detailed requirements should be given, helping users in choosing the best algorithms and data structures for each particular application. See also Dave Musser's Dagstuhl lecture abstract.

Open Problem: Develop a better way of expressing performance requirements than O-notation

[Musser] Again, see Dave Musser's Dagstuhl lecture abstract.


 

Prev Up