An Introduction to Generic Programming


Concept refinement enables more and better algorithms, because the refining concept introduces more operations that describe richer abstractions. Much of the time, these additional operations permit the implementation of new algorithms, e.g., where BidirectionalIterator allowed the efficient implementation of the reverse() algorithm. However, refinements can also allow certain algorithms available for the refined concept to be more implemented more efficiently with the refining concept.

Let us consider a Polygon concept. We could imagine that there are two important operations for a Polygon: one, num_sides(), which returns the number of sides in the polygon; and two, side_length(i), which returns the length of the ith side. We can compute the circumference of a Polygon in linear time:

// Requirements: Polygon

template double circumference(P p) { double result = 0; for (int i = 0; i < num_sides(p); ++i) result += side_length(p, i); return result; }

We can create a concept EquilateralPolygon that refines Polygon, but where all sides have the same length. Thus,we can use the circumference() algorithm above on any EquilateralPolygon. However, we can do better, because one can compute the circumference of an EquilateralPolygon in constant time with the following algorithm:

// Requirements: EquilateralPolygon

template double circumference(P p) { return num_sides(p) * side_length(p, 0); }

We now have two implementations of circumference() that differ only in their requirements. Generic Programming requires that the most specific of these implementations should always be chosen, a feature that is sometimes referred to as concept-based overloading. For instance, if an abstraction is an EquilateralPolygon, the constant-time algorithm should be used; otherwise, we will fall back to the linear-time algorithm. In C++, this can be accomplished with a technique called tag dispatching, which we will not detail here.

Concept-based overloading ensures that the most efficient implementation available for an algorithm is always used. This behavior is particularly useful in combatting certain cases of over-generalization, where lifting an algorithm to make it more general would also make it less efficient. For instance, the lower_bound() algorithm of the Standard Template Library has a very curious complexity clause:

The number of comparisons is logarithmic: at most log(last - first) + 1. If ForwardIterator is a Random Access Iterator then the number of steps through the range is also logarithmic; otherwise, the number of steps is proportional to last - first.

lower_bound() is a binary search, but it can be implemented with only a Forward Iterator. Doing so requires linear time, because we need to step through the elements of the sequence one by one. However, if the algorithm is given a Random Access Iterator, it can jump around the sequence and therefore requires only a logarithmic number of steps. In the STL, this is accomplished through specialization of the advance() and distance() functions, which move an iterator forward a number of steps or compute the number of elements between two iterators, respectively. By using these utility algorithms, the STL is able to lift lower_bound() from an algorithm that requires Random Access Iterators to one that only requires Forward Iterators, without sacrificing performance in the Random Access Iterator case.

Previous: Models Author: Douglas Gregor Next: Conclusion