Implications of STL for CS-2

Joel C. Adams
Department of Computer Science
Calvin College
February 1997

First Things First

When considering changes to our computer science curriculum, our guiding principle should be:

What will best serve our students?

With the availability of the standard template library (STL) for C++, we believe that our students are best served by a CS-2 course that is significantly different from the traditional Pascal-era course.

A Continuum of Approaches

Since the adoption of STL in C++, there is a continuum of possible ways to teach CS-2. One endpoint of this continuum would seem to be a black box approach that emphasizes the use of the "off-the-shelf" data structures provided by STL without examining their implementation. The other endpoint of this continuum appears to be a no box approach that emphasizes the traditional implementation of data structures from scratch, without coverage of STL. (Such a course would be quite similar to the traditional Pascal-era course.)

We advocate a glass box approach, in which traditional data structures are the primary focus of CS-2, but we use and "peek under the hood" of their STL counterparts to study their implementation, and implement some data structures ourselves. Our position is thus one of the many "middle ground" positions between the two extreme endpoints.


Our reasons for rejecting the "black box" and "no box" approaches in favor of our "glass box" approach are as follows:

A Glass Box Approach: Data Structures

It should be apparent that if CS-2 is already a "full" course, then it is not feasible to cover all of the "new" STL-related topics and all of the "old" topics that are traditionally covered in CS-2. After careful analysis of what we were trying to accomplish with CS-2, we arrived at the syllabus below. At Calvin College, CS-2 receives 4 hours of credit, with three lecture hours and a two hour closed laboratory session each week.

WeekGeneral Topic
1Review C++ and Classes
2Introduction to Pointers, Indirection and Iterators
3Pointers and vector Implementation
4Introduction to Derivation and Inheritance
5Introduction to Polymorphism
6Introduction to Lists
7list Implementation
8Algorithm Analysis and Complexity
9Introduction to Hashing
10Implementing Hash Tables
11Introduction to Trees
12Sets and set Implementation
13Dictionaries and map Implementation

Much of the treatment of specific topics is integrated throughout the course, using the "spiral" approach. For example, pointers are introduced early (motivated by the run-time flexibility of a vector), and subsequently used in studying polymorphism and the implementations of the various STL components. Similarly, algorithm complexity is introduced near the middle of the course (motivated by discussing the difference of inserting into a vector or list), and subsequently used to motivate hash tables, sets and maps.

A Glass Box Approach: Algorithms

To "make room" for the STL topics in CS-2, we have shifted much of the algorithm-specific material (e.g., sorting) to a new "CS-3" course titled Algorithms and Data Structures. This course applies our "glass box" approach to the study of algorithms, "looking under the hood" of the STL algorithms templates when applicable.

For course projects, our CS-3 course introduces additional data structures that are not provided by STL (e.g., graphs), and implements class templates for such objects, and implements algorithm templates by which they can be processed.

Other Position Papers

For more information about Computer Science at Calvin College, contact Joel Adams (
Last modified: Feb 18, 1997.