Component Development within the STL Framework

Project: Domain-specific STL-like libraries

Project: Develop container traits

Project: Regular expression search

Project: Iterators for 2-level structures

[Stepanov] Already well along at SGI. Matt Austern's Dagstuhl lecture reported considerable progress. See also NUMA iterators.

Project: Design and implement trie-based associative containers

[Stepanov]

Project: Provide an alternative implementation of sorted-associative containers based on skip-lists

[Stepanov]

Project: Provide an alternative implementation of sorted-associative containers based on vectors

[Stepanov]

Project: Design and implement N-ary trees

[Stepanov]

Project: Design and implement a generic version of the Boyer-Moore searching algorithm

[Stepanov] Dave Musser and Gor Nishanov have essentially solved this problem, with a fast generic sequence searching algorithm obtained by combining the Knuth-Morris-Pratt algorithm with a hashed version of Boyer and Moore's skip loop.

Project: Provide versions of all STL algorithms with O(N logN) or better worst-case time bounds

[Musser and Stepanov] This project is almost complete, with Musser's introsort algorithm replacing the original quicksort implementation of sort, and the Musser-Nishanov algorithm replacing the original straightforward sequence search algorithm. The only remaining algorithm with an O(N²) worst-case time bound is the Hoare find algorithm used to implement nth_element. This can be replaced by some variant of Musser's introselect algorithm, but some experimentation remains to be done.

Project: Provide forward iterator versions for all of the STL algorithms

[Stepanov] For example, a new implementation of stable_sort should be developed that works on forward iterators and improves its cache behavior by using binary-counter instead of parallel-reduction merging.

Project: Add 3-way comparison versions of all STL components that take comparisons

[Stepanov]

Project: Add iterator adaptors

[Stepanov] Examples:

• restrictors (forward, bidirectional)
• const_iterator (*i = const)
• int_iterator
• stride_iterator
• filtering_iterator
• transform_iterator

Project: Define function_traits and re-implement function objects using them

[Stepanov]

Project: Provide parallel versions of important STL algorithms

[Stepanov] This assumes a solution for the NUMA-iterator problem.