Generic Programming

David R. Musser

Last updated: May 19, 2003

My working definition of generic programming is "programming with concepts," where a concept is defined as a family of abstractions that are all related by a common set of requirements. A large part of the activity of generic programming, particularly in the design of generic software components, consists of concept development--identifying sets of requirements that are general enough to be met by a large family of abstractions but still restrictive enough that programs can be written that work efficiently with all members of the family. The importance of the C++ Standard Template Library, STL, lies more in its concepts than in the actual code or the details of its interfaces. Currently the most thorough development and exposition of the STL concepts is the Silicon Graphics Inc. STL web site, where the STL container and iterator concepts are especially well developed and documented. At Rensselaer, we have begun development of an extensive Algorithm Concept taxonomy, currently emphasizing algorithms found not only in STL but also in the Boost Graph Library (BGL), developed by Andrew Lumsdaine's group at Indiana University.

My current research is largely focused on generic programming technology, including theory, concept development/formalization, and component development. Some of the new or improved generic components developed here are made available via this web site for general use. Links are also provided to other generic programming-related papers and web sites (that I've been involved in writing or creating; there's no attempt to provide a comprehensive set of links).

  • Generic Algorithms
  • Adaptors
  • Performance Measurement Adaptors
  • Complete Traversal Adaptors and Algorithms
  • Literate Generic Programming
  • Formal Specification of STL Container and Iterator Concepts
  • Anatomy of a List Class
  • A Portable Cache Profiler
    Based on Source-Level Instrumentation
  • Results of a Generic Programming Workshop
  • Goals, Participants, and Lecture Abstracts
  • Projects and Open Problems