Generic Libraries in C++
Not every library using C++ templates already deserves the attribute generic. In the following subjective selection I focus on how general the underlying mathematical concepts are reflected in the software (and whether these concepts are explicitly dealt with). So, my litmus test is the following:
This, evidently, is a quite challenging requirement. To get near to it, a thorough analysis of the foundational concepts of the application domain is necessary. A practical implementation has to weigh the cost against benefit. Thus, genericity is not an absolute, on-off property of software, but rather a gradual quality. This is analogous to the differing level of abstraction also present in mathematical concepts.
What can be expected, however,
is an effort to remove dependencies
on arbitrary implementation decisions (e.g. we ask for
array::size(), but the user offers
array::length()).
Because of such freedom in implementing abstract concepts,
we cannot demand
that all user objects that are "suitable in principle"
can be passed as is to a generic component.
But it should be possible at least in principle
to design light-weight adapters for the arguments
if the underlying abstractions match
(and the generic component should make this easy).
And now, on to concrete examples ...
This compilation is sorted by application domain: linear sequences, graphs, geometry and image processing.Libraries for linear sequences: The Standard Template Library & Co
The best known exemplar of a generic library is the Standard Template Library (STL), part of the C++ standard library since 1998. The STL is mostly the work of Alexander Stepanov, building on his prior work with David Musser. The STL abstracts sequence data types (like arrays or lists) and corresponding algorithms (like searching, sorting and comparing). Iterators proved the link between sequences and algorithms. An iterator is an abstract interface for the basic functionality navigation and data access. Categories of sequences with special properties, like bidirectional or random access navigation, are modeled by corresponding iterator categories. Thus, more efficient algorithms can be selected if available for special cases. It turns out that only 5 different iterator categories are needed in total.
Strictly speaking, "the" STL is not a library but a specification (in the C++ standard), of which a number of implementations exist. First of all, every standard-conforming C++ compiler comes with a standard library containing the STL. In addition, there are a number of popular implementations, like the SGI STL or STLport, which contains a debug mode.
Many books and online documentation describes the STL. A good (though slightly out-of-date) online resource is the STL documentation by SGI from around 1998, when Alexander Stepanov worked for SGI. A good introduction is the book of Nicolai Josuttis:
-
The C++ Standard Library - A Tutorial and Reference.
2nd Edition.
Addison Wesley
2012
The 2nd Edition covers C++11.
Libraries for Graphs
The Boost Graph Library covers graphs and graph algorithms. The abstractions of the BGL build on those of the STL. There are iterators over graph nodes and edges, but in addition, local iterators over incoming and outgoing edges of a node. Data associated to nodes and edges are modeled by properties. Thus, the concerns of navigation and data access are separated (in contrast to the STL, where both are combined in the iterator concept). The BGL has a good online documentation and is described in the book by Jeremy Siek:
-
The Boost Graph Library.
User Guide and Reference Manual.
Addison Wesley
2002
Also from Boost, a parallel extension of the BGL is available.
Libraries for geometric data structures and algorithms
Geometric data structures and algorithms are the topic of the Computational Geometry Algorithms Library (CGAL) and the Grid Algorithms Library (GrAL).
The Computational Geometry Algorithms Library CGAL is a large library dealing with all kinds of geometric and combinatoric data structures and algorithms. From what I have seen, many of the non-trivial algorithm implementations seem to work with CGAL's own data structures only. For instance, the computation of 2D polygon intersections only works for built-in data structures like Polygon_2. These are parameterized, but user-defined data structures can be used only at the cost of a complete copy.
The Grid Algorithms Library GrAL (my own development) has a narrower scope than CGAL and focuses on grids (meshes) of arbitrary dimension exclusively. A simple example is a triangle mesh; mathematically, these things are called cellular complexes. For a 2-dimensional mesh, the basic entities are vertices, edges, and cells (faces), and it is actually a planar graph. Similar to the Boost Graph Library, GrAL defines global and local (neighborhood) iterators, though there are considerable more of the latter. Data on mesh elements is modeled by grid functions, which play a role similar to BGL's property maps. An important special case are Cartesian meshes (or grids), which are in a sense analogous to random access sequences in the STL. A number of algorithms (especially those involving geometric searching) can be implemented more efficiently on Cartesian grids.
Libraries for image processing
For the field of image processing, several libraries are available, which are generic to varying degrees: There is VIGRA, the Generic Image Library (GIL) and the ITK (Imaging Toolkit).
The library VIGRA (Vision with Generic Algorithms) was developed by Ulrich Koethe. It works on image data structures for arbitrary dimension (though 2D images still form an important special case) and offers a considerable number of generically implemented image processing algorithms. The essential abstraction mechanisms involve iterators with either multidimensional offsets or nested (hierarchical) by dimensions, and data accessors encapsulating access to image data (pixels in 2D). Using accessors, also multi-banded images can be processed using the same generic algorithm. Accessors are similar to BGLs properties or GrAL's grid functions. Actually, it is straightforward to map GrAL Cartesian grids and grid functions to VIGRA images, and vice versa.
The Generic Image Library (GIL) was developed by Adobe and is now a part of Boost. What in VIGRA is a multidimensional iterator, is called locator in GIL because it does not define linear increment and decrement. GIL defines formal concepts analogous to the STL in a way that template parameters can be checked automatically by the compiler. This being the focus of the library developers, only very few actual algorithms are implemented. Since 2007, development seems to have stopped.
One of the best known C++ image processing libraries is ITK (Insight Toolkit) of the US National Library of Medicine. ITK offers a truly large choice of image processing algorithms. Its image data structures are parameterized and dimension independent. As the implementation of the algorithms is tied to those data structures, the genericity of ITK is however rather limited.