Chapter 1: Preliminaries

Generic Programming
Part I: Fundamental Concepts

Chapter 1: Preliminaries

Last updated 26 March 1998

They came [to Plato's lecture on the Good] in the conviction that they would get some one or other of the things that the world calls good: riches, or health, or strength. But when they found that Plato's reasonings were of mathematics their disenchantment was complete.

(Aristoxenus, Harm. El. 2.30, trans. Ross)

Section 1.1: Introduction

Genesis and contents. Objectives and motivation: reusability and performance.

Section 1.2: A Motivating Example -- Swap

Section 1.3: Background Definitions

Section 1.4: C++ Requirements

The underlying algorithmic language we use requires only very simple constructs, namely if, while, do while, function call, return, and block statements, along with the operations (functions) required by the algorithms we are implementing.

Develop the STL pair structure as an example.

Section 1.5: Conventions

There are a number of conventions we will follow throughout this book.

Parts of the book are mathematical or discuss analogies with mathematical concepts, but are not critical to understanding of the material. We set those parts in a smaller font to distinguish them.

The use of code examples, both good and bad, is critical to our exposition. We will distinguish incorrect code by setting it in red.

Implementation Queue

The following are points to be integrated somewhere:

Although this book is based on C++, we will often discuss the development of language features over time, using examples from previous languages. However, this is not a book about the history of programming languages, and we choose our example languages for their familiarity to a large number of programmers, and not necessarily because they represent the first or most important occurrence of the feature being discussed.

There are two kinds of complexity propositions: requirements on the operations in the concepts and algorithmic guarantees of algorithms defined on the concept. (Of course, both of these have worst case and average case kinds.)

Send comments about this page to Jim Dehnert or Alex Stepanov.