Many problems in generic programming arise from the fact that one has to deal with heterogeneity introduced by the representation of data. For example, in the generic implementation of grid functions, one has to take different action depending on whether the elements are consecutively numbered or not (a semantic heterogeneity). Also, the number of elements of a given type in a grid is accessed by different functions (a syntactic heterogeneity).
We have overcome these heterogeneities by collecting the relevant information about element types in element traits mentioned before. On a higher level, an algorithm using grid functions does not have to bother with these details, as grid functions offer a completely uniform way of dealing with data associated to grid elements.
This is an example of what can be called homogenization: Heterogeneous properties of entities playing the same role (grid elements and their handles) are hidden by a uniform interface (traits::size(grid_t const&)) or dealt with at the next higher level (grid functions), and thus do not propagate any further.
This approach crucially depends on a specialization mechanism, or still better, partial specialization. The common conception of C++ templates as just a kind of macro turns out to be a misconception at this point.
The art, of course, consists in identifying a small number of key properties that allow to capture the essential differences of representations. For grid elements, one such key property is whether or not they are numbered (stored) consecutively.
A related problem is the adaptation of algorithms to the capabilities of data structures. An extreme case is a testing function for grid data structures: Here, we want to use exactly those concepts implemented by the data structure. A generic implementation of such a testing procedure would have to automatically adapt to the set of supported concepts. This could be achieved by breaking down the algorithm in `atomic' pieces and put them together, based on compile-time information whether a certain feature (e. g. iterator) exists or not.
A third difficulty is the decision of what to parameterize.
As many algorithms internally use a lot of data structures which
could possibly affect their performance or execution,
these could be made parameters as well.
However, this leads to blown-up interfaces,
which leave many of the
decisions (and possibilities of making mistakes) to the user.
We have experimented with a layering of interfaces,
from minimal to maximal parameterization,
to alleviate the problem.
If there are many potential parameters,
a more systematic approach is needed to organize them,
especially sensible defaults.