Specialization
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.
|