Generic Programming:
Objectives and Sketch

Last updated 16 March 1998


This book is being derived from a class on generic programming first taught by Alex Stepanov at SGI in 1997. It is intended to be a practical guide and motivation for practicing programmers, in the form of the original class, based on extensive examples drawn from the C++ Standard Template Library. The approach is the progressive development of a variety of important generic examples, with attention to the underlying history, complexity, and performance.


Part I: Fundamental Concepts

Chapter: Preliminaries

The book's objectives, genesis, and contents. General motivation -- reusability and performance. A simple motivating example, e.g. swap. Background definitions. C++ requirements? Conventions.

Chapter: Fundamentals

Interrelation of equality, assignment, and construction. The notion of regular types. The notion of parts. The taxonomy of objects and their parts. Swap algorithm. Generic optimizations on regular types. Ordering relations. Strict weak ordering. Total ordering. Min and max algorithms.

Chapter: Software Components

Taxonomy of software components. Function objects. Function object adapters. Binding and composition. Components traits. Categories and category dispatching.

Part II: Algorithms on Algebraic Structures

The material in this part is mathematical in nature, and may be skipped without significant effect on the remainder of the book.

Chapter: Arithmetic

Power. Russian peasant algorithm. Fibonacci numbers. Fiduccia's algorithm for linear recurrences. GCD. Euclid's algorithm. Stein's algorithm. Extended Euclid's algorithm. Continued fractions.

Chapter: Algebra and Number Theory

Algebraic structures: monoids, semigroups, groups, rings, fields. Finite groups: order of group, subgroup, element, and generators. Euler's theorem. Modular arithmetic. Prime numbers and primality testing. Miller-Rabin's algorithm.

Chapter: Encryption

The RSA encryption algorithm.

Part III: Algorithms on Sequential Structures

A focus of this part is how data access capabilities (iterators) affect the available algorithms and complexity for various problems, and how one can adapt the algorithms used to the capabilities available at compile-time instead of making more expensive choices at runtime.

Chapter: Iterators

Linear search algorithm (find). Copy algorithm. Iterator axioms and models. Iterator categories: input, output, forward, bidirectional, random access. Iterator traits and compile-time dispatch. Iterator adapters. Reverse iterator. Stride iterator.

Chapter: Permutations

What is a permutation? Classification: Index-based, value-based, and comparison-based. Cycle decompositions. The computational complexity of a permutation.

Chapter: Index- and Value-Based Permutation Algorithms

Reverse algorithms. Memory-adaptive algorithms. In-place rotation: Gries-Mills algorithm, 3-reverse algorithm, and GCD-cycles algorithm. Stability of permutations and pseudo-permutations. Remove and stable remove. Partition algorithms: Hoare partition, Lomuto partition, stable partition. Random shuffling and random selection. Lo-Ho algorithm. Reduction, parallel reduction, and binary-counter reduction. NUMA-iterators.

Chapter: Sorting And Related Algorithms

Binary Search. Lower and upper bound algorithms. Merging and set operations. In-place merging. Memory-adaptive merging. Stable sorting. Priority queues and partial sorting. Musser's introsort. Binomial forests.

Part IV: Data Structures and Containers

Chapter: Data Structure Principles

Data structures and their iterators. Container requirements.

Chapter: Sequential Data Structures

Sequences. Vectors. Lists. Dequeues.

Chapter: Associative Data Structures

Associative containers.

Part V: Programming Languages and Software Engineering

Compiler optimization issues. Why don't we use inheritance? Limitations of C++. Concepts as a linguistic entity. Compiling generic components. Science is a necessary foundation of engineering.

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