Last updated 16 March 1998

Objectives

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.

Issues:

• This is fundamentally a software engineering book. It should be quite appropriate for an advanced programming course. It might also be a reasonable text for classes on algorithms and data structures. Should that be an objective? It wouldn't be a traditional algorithms text, since we don't want to do rigorous complexity analysis.

• Do we want to discuss and/or develop NUMA iterators somewhere?

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.

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