The Standard Template Library and its Java equivalent, the Java Generic Library, here referred to collectively as STL, present new challenges for the data structures course. I take the following positions in relation to CS2:
1. Students of computer science must be able to build any reasonable data structure. (note emphasis).
2. Students of computer science must be able to use standard library components effectively.
3. Students of computer science must be able to build large programs in teams.
4. Students must understand algorithm efficiency and be able to evaluate data structures accordingly.
5. Students must understand and use modern concepts of encapsulation and parameterization such as interfaces, classes, and generics.
Not all data structures need be actually built by the students and certainly not all data structures used by the students must be built by themselves and their colleagues. But they must be taught to do these things in such a way that it doesn't conflict with the other goals.
One way to achieve all of the above goals is to have the students examine and develop large parts of a library that meets many of the design criteria of the STL. While the set container of the STL may be beyond a sophomore student, the principles that it implements are not. Students can build balanced binary search trees and evaluate their performance.
The STL forms a suitable outline of a course in data structures. It is missing a few parts (hash tables and graphs) that can be easily added within the spirit of the STL and/or built from standard STL components. The team aspects of software design can be met by having groups of students work on parts of a design. Extending the STL with hash tables is a marvelous team project that can be entered into in competition between different teams. For example there are several variations on self reorganizing hash tables that provide subtly different problems and result in slight performance differences.
Conclusions.
The STL should be used in the data structures course. It should not just be examined, however. Students should build structures that are similar to STL in flavor, design, and efficiency, though not with quite the same degree of integration and sophistication. The sophistication level should, however be sufficient that the STL itself can be understood and utilized. Students should use the STL itself for projects and as the basis of extension. Students should do this in teams. The course has three interleaved parts, all essential:
1. Building properly encapsulated and parametrized structures and associated algorithms.
2. Understanding STL (or other standard libraries)
3. Using the libraries in (team) projects.