Algorithm Library Design
Lecture Notes

© Lutz Kettner. 1st Edition, May 2000
University of North Carolina at Chapel Hill

Course home page: http://www.mpi-sb.mpg.de/~kettner/courses/lib_design_03/

Table of Contents

• Preface
• 1. Introduction
• 2. The C++ Language
• 3. STL and Generic Programming
• 4. Design Strategies
• 5. Advanced C++ Programming
• 6. CGAL, the Computational Geometry Algorithms Library
• 7. Design Patterns
• 8. Template Metaprograms
• 9. Large Scale C++ Software Design
• 10. Overview of Some Foundation Libraries
• References

Extended Table of Contents

• Preface
• 1. Introduction
  • Motivation
  • Generative Programming
  • Feature Modeling
  • Brain Storming
  • Feature Starter Sets
  • Odds and Ends
• 2. The C++ Language
  • Introduction
  • Classes and Member Functions
  • Constructors, Assignment, and Destructor
  • Automatic Conversion and the explicit Keyword for Constructors
  • Ambiguity between Function-Style Cast and Declaration
  • Derivation
  • Virtual Member Functions
  • Static Class Members
  • Templates
  • "Lazy" Implicit Instantiation
  • Member Templates
  • Specialization and Partial Specialization
  • Local Types and Keyword typename
  • Dynamic and Static Polymorphism
  • Name Spaces
• 3. STL and Generic Programming
  • Introduction
  • Concept and Model
  • Generic Algorithms Based on Iterators
  • A First Partial Implementation of an Iterator
  • Function Objects
  • Iterator Traits
  • Implementing Adaptable Function Objects
  • Implementation of the Iterator Adaptor back_inserter
  • More Iterators
  • Function Dispatch using Iterator Category at Compile Time
• 4. Design Strategies
  • Domain Design
  • Domain Specific Languages
  • Configuration DSLs
  • Policy-Based Class Design
  • Enriched Policies
  • Combining Policies
  • Named Template Arguments
  • GenVoca Architecture
  • GenVoca Example: List
  • Implementing a GenVoca Architecture
  • Generators
• 5. Advanced C++ Programming
  • Introduction
  • Automatic Library Initialization and Housekeeping
  • Const Correctness
  • Proxy Classes
  • Smart Pointers
  • Smart Pointers: std::auto_ptr<T>
  • Smart Pointers: Polymorphic Deep Copy
  • Smart Pointers: Reference Counting
  • Exception Safety
  • Associating Data to Items in a Data Structure
  • Solving Mutual Dependencies with the Barton-Nackman Trick
  • Solving Mutual Dependencies between Class Templates
  • Double Dispatch, Making a Function Virtual for Two Arguments
• 6. CGAL, the Computational Geometry Algorithms Library
  • Introduction
  • Related Work
  • Overview of the Library Structure
  • Geometric Kernel
  • Basic Library
  • Geometric Traits Classes
• 7. Design Patterns
  • Introduction
  • Abstract Factory Pattern
  • Singleton Pattern
  • Adaptor Pattern (a.k.a. Wrapper Pattern)
  • Visitor Pattern
  • CGAL::Object, a Polymorphic Type in CGAL
• 8. Template Metaprograms
  • Introduction
  • Compile-time programming
  • Constraining templates using the SFINAE principle
  • Type classification
  • Self Reflection of Types in C++: The flatten.C Example
  • Expression Templates
• 9. Large Scale C++ Software Design
  • Introduction
  • Internal and External Linkage
  • Components and Dependency Relations
  • Physical Hierarchy
  • Reducing Link-Time Dependencies: Levelization
  • Reducing Compile-Time Dependencies: Insulation
• 10. Overview of Some Foundation Libraries
  • Introduction
  • Gnu C++ Library
  • Tools.h++
  • Booch Components
  • LEDA, the Library of Efficient Datatypes and Algorithms
• References