**Go backward to **...

**Go up to **Library Development

### Component Development within the STL Framework

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

[Stepanov]

[Stepanov]

[Stepanov]

[Stepanov]

[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.

[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*^{2}) 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.

[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.

[Stepanov]

[Stepanov] Examples:

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

[Stepanov]

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