|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.
The book's objectives, genesis, and contents. General motivation -- reusability and performance. A simple motivating example, e.g. swap. Background definitions. C++ requirements? Conventions.
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.
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.
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.
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.
The RSA encryption algorithm.
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.
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.
What is a permutation? Classification: Index-based, value-based, and comparison-based. Cycle decompositions. The computational complexity of a permutation.
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.
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.
Data structures and their iterators. Container requirements.
Sequences. Vectors. Lists. Dequeues.
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|