T.gp: Generic programming

Generic programming is programming using types and algorithms parameterized by types, values, and algorithms.

T.1: Use templates to raise the level of abstraction of code

Reason

Generality. Re-use. Efficiency. Encourages consistent definition of user types.

Example, bad

Conceptually, the following requirements are wrong because what we want of T is more than just the very low-level concepts of "can be incremented" or "can be added":

template<typename T, typename A>
    // requires Incrementable<T>
A sum1(vector<T>& v, A s)
{
    for (auto x : v) s+=x;
    return s;
}

template<typename T, typename A>
    // requires Simple_number<T>
A sum2(vector<T>& v, A s)
{
    for (auto x : v) s = s + x;
    return s;
}

Assuming that Incrementable does not support + and Simple_number does not support +=, we have overconstrained implementers of sum1 and sum2. And, in this case, missed an opportunity for a generalization.

Example

template<typename T, typename A>
    // requires Arithmetic<T>
A sum(vector<T>& v, A s)
{
    for (auto x : v) s+=x;
    return s;
}

Assuming that Arithmetic requires both + and +=, we have constrained the user of sum to provide a complete arithmetic type. That is not a minimal requirement, but it gives the implementer of algorithms much needed freedom and ensures that any Arithmetic type can be used for a wide variety of algorithms.

For additional generality and reusability, we could also use a more general Container or Range concept instead of committing to only one container, vector.

Note

If we define a template to require exactly the operations required for a single implementation of a single algorithm (e.g., requiring just += rather than also = and +) and only those, we have overconstrained maintainers. We aim to minimize requirements on template arguments, but the absolutely minimal requirements of an implementation is rarely a meaningful concept.

Note

Templates can be used to express essentially everything (they are Turing complete), but the aim of generic programming (as expressed using templates) is to efficiently generalize operations/algorithms over a set of types with similar semantic properties.

Enforcement

• Flag algorithms with "overly simple" requirements, such as direct use of specific operators without a concept.
• Do not flag the definition of the "overly simple" concepts themselves; they may simply be building blocks for more useful concepts.

T.2: Use templates to express algorithms that apply to many argument types

Reason

Generality. Minimizing the amount of source code. Interoperability. Re-use.

Example

That's the foundation of the STL. A single find algorithm easily works with any kind of input range:

template<typename Iter, typename Val>
    // requires Input_iterator<Iter>
    //       && Equality_comparable<Value_type<Iter>, Val>
Iter find(Iter b, Iter e, Val v)
{
    // ...
}

Note

Don't use a template unless you have a realistic need for more than one template argument type. Don't overabstract.

Enforcement

??? tough, probably needs a human

T.3: Use templates to express containers and ranges

Reason

Containers need an element type, and expressing that as a template argument is general, reusable, and type safe. It also avoids brittle or inefficient workarounds. Convention: That's the way the STL does it.

Example

template<typename T>
    // requires Regular<T>
class Vector {
    // ...
    T* elem;   // points to sz Ts
    int sz;
};

vector<double> v(10);
v[7] = 9.9;

Example, bad

class Container {
    // ...
    void* elem;   // points to size elements of some type
    int sz;
};

Container c(10, sizeof(double));
((double*)c.elem)[] = 9.9;

This doesn't directly express the intent of the programmer and hides the structure of the program from the type system and optimizer.

Hiding the void* behind macros simply obscures the problems and introduces new opportunities for confusion.

Exceptions: If you need an ABI-stable interface, you might have to provide a base implementation and express the (type-safe) template in terms of that. See Stable base.

Enforcement

• Flag uses of void*s and casts outside low-level implementation code

T.4: Use templates to express syntax tree manipulation

Reason

???

Example

???

Exceptions: ???

T.5: Combine generic and OO techniques to amplify their strengths, not their costs

Reason

Generic and OO techniques are complementary.

Example

Static helps dynamic: Use static polymorphism to implement dynamically polymorphic interfaces.

class Command {
    // pure virtual functions
};

// implementations
template</*...*/>
class ConcreteCommand : public Command {
    // implement virtuals
};

Example

Dynamic helps static: Offer a generic, comfortable, statically bound interface, but internally dispatch dynamically, so you offer a uniform object layout. Examples include type erasure as with std::shared_ptr’s deleter. (But don't overuse type erasure.)

Note

In a class template, nonvirtual functions are only instantiated if they're used -- but virtual functions are instantiated every time. This can bloat code size, and may overconstrain a generic type by instantiating functionality that is never needed. Avoid this, even though the standard facets made this mistake.

Enforcement

• Flag a class template that declares new (non-inherited) virtual functions.