15. Templates

There is nothing more difficult to carry out, nor more doubtful of success, nor more dangerous to handle, than to initiate a new order of things.

– Niccolo Macchiavelli

Support for parameterized types — class templates — constraints on template arguments — avoiding storage overhead — function templates — deducing function template arguments — explicit specification of function template arguments — conditionals in templates — syntax — composition techniques — relationships among template classes — member templates — template instantiation — name binding in templates — specialization — explicit instantiation — a model for templates in files — importance of templates.

The roots of templates lie in the wish to express parameterization of container classes. Exceptions come from a desire to provide a standard way to handle run-time errors. In both cases, the mechanisms inherited from C were in actual use found to be too primitive. The C features didn’t allow programmers to directly express their aims and didn’t interact well with key features of the C++ language. We had used macros to parameterize containers since the earliest days of C with Classes (§2.9.2), but C macros fail to obey scope and type rules and don’t interact well with tools. The mechanisms used for error handling in early C++ such as setjmp/longjmp and error indicators (for example, errno) don’t interact well with constructors and destructors.

The lack of these features led to warped designs, to unnecessarily low-level coding styles, and eventually to problems with combining libraries from more than one provider. In other words, the absence of these features made it unnecessarily difficult for people to maintain a consistent (high) level of abstraction.

To my mind, templates and exceptions are two sides of the same coin: templates allow a reduction in the number of run-time errors by extending the range of problems handled by static type checking; exceptions provide a mechanism for dealing with the remaining run-time errors. Templates make exception handling manageable by reducing the need for run-time error handling to the essential cases. Exceptions make general template-based libraries manageable by providing a way for such libraries to report errors.

Templates were considered essential for the design of proper container classes. I first presented the design for templates at the 1988 USENIX C++ conference in Denver [Stroustrup, 1988b]. I summarized the issues like this:

“In the context of C++, the problems are

[1] Can type parameterization be easy to use?

[2] Can objects of a parameterized type be used as efficiently as objects of a “hand-coded” type?

[3] Can a general form of parameterized types be integrated into C++?

[4] Can parameterized types be implemented so that the compilation and linking speed is similar to that achieved by a compilation system that does not support type parameterization?

[5] Can such a compilation system be simple and portable?”

These were my design criteria for templates. Naturally, my answer to all these questions was yes. I stated the fundamental design alternatives like this:

“For many people, the largest single problem using C++ is the lack of an extensive standard library. A major problem in producing such a library is that C++ does not provide a sufficiently general facility for defining “container classes” such as lists, vectors, and associative arrays. There are two approaches for providing such classes/types:

[1] The Smalltalk approach: rely on dynamic typing and inheritance.

[2] The Clu approach: rely on static typing and a facility for arguments of type type.

The former is very flexible, but carries a high run-time cost, and more importantly defies attempts to use static type checking to catch interface errors. The latter approach has traditionally given rise to fairly complicated language facilities and also to slow and elaborate compile/link time environments. This approach also suffered from inflexibility because languages where it was used, notably Ada, had no inheritance mechanism.

Ideally, we would like a mechanism for C++ that is as structured as the Clu approach with ideal run-time and space requirements, and with low compile-time overheads. It also ought to be as flexible as Smalltalk’s mechanisms. The former is possible; the latter can be approximated for many important cases.”

Thus, the key issues were seen to be notational convenience, run-time efficiency, and type safety. The main constraints were portability and reasonably efficient compilation and linkage – including the instantiation of template classes and functions directly or indirectly used in a program.

The key activity in determining what we needed from a parameterized type facility was to write programs using macros to fake parameterized types. In addition to me, Andrew Koenig, Jonathan Shopiro, and Alex Stepanov wrote many template-style macros to help determine what language features were needed to support this style of programming. Ada didn’t feature in my thinking about templates except as the source of my dislike for template instantiation operators (§15.10.1). Alex Stepanov knew Ada well, though, and some Ada styles may have entered our thinking through his examples.

The earliest implementation of templates that was integrated into a compiler was a version of Cfront that supported class templates (only) written by Sam Haradhvala at Object Design Inc. in 1989. This version was later expanded into a full implementation by Stan Lippman and supported by a template instantiation mechanism designed by Glen McCluskey with input from Tony Hansen, Andrew Koenig, Rob Murray, and me [McCluskey, 1992]. Mary Fontana and Martin Neath from Texas Instruments wrote a public-domain preprocessor that implemented a variant of templates [Fontana, 1991].

These and other implementations gave us significant experience. However, I and others were still nervous about putting something not completely well-understood into a standard, so the template mechanism defined in the ARM was deliberately minimal. It was understood at the time that it was probably too minimal, but it is much harder to remove unfortunate features than to add features shown to be needed.

The template mechanisms presented in the ARM were accepted by the ANSI C++ committee in July 1990. An important argument for the acceptance of templates into the draft standard was the observation that the committee members discussing the issue in a working group found that among ourselves, we had more than half a million lines of C++ using templates and “fake templates” in real use.

In retrospect, templates fell into a crack between two strategies for refining the design of a new C++ language feature. Before templates, I refined all features through a process of implementation, use, discussion, and reimplementation. After templates, features were extensively discussed in the standards committee and usually implemented concurrently with that discussion. The discussion about templates wasn’t as extensive or wide-ranging as it ought to have been, and I lacked the crucial implementation experience. This has led to a revision of many aspects of templates based on implementation and usage experience. For post-exception-handling extensions, I have resurrected the practice of acquiring personal implementation experience as a key design activity.

Despite their rough corners and need for revision, templates did what they were supposed to do. In particular, templates allowed efficient, compact, and type-safe C++ container classes to be designed and conveniently used. Without templates, design choices were being pushed towards weakly typed or dynamically typed alternatives to the detriment of both program structure and efficiency.

I do, however, think that I was too cautious and conservative when it came to specifying template features. I could have included features such as explicit specification of function template arguments (§15.6.2), deduction of non-type function template arguments (§15.6.1), and nested templates (§15.9.3). These features would not have added greatly to the burden of the implementers, and users would have been helped. On the other hand, I failed to give enough guidance and support to implementers in the area of template instantiation (§15.10). What I cannot know is whether I would have done more harm than good had I proceeded with the design of templates without the benefit of experience that implementation and use of the initial design have given me.

The presentation here reflects the state of affairs after much experience has been gained and resolutions reflecting this experience passed by the ANSI/ISO standards committee. The name binding rules, the explicit instantiation mechanism, the restrictions on specialization, and the explicit qualification of template function calls were voted into C++ at the San Jose meeting in November 1993 as part of a general cleanup of the definition of templates.

The discussion of templates is organized like this:

§15.3	Class Templates.
§15.4	Constraints on Template Arguments.
§15.5	Avoiding Code Replication.
§15.6	Function Templates.
§15.7	Syntax.
§15.8	Composition Techniques.
§15.9	Template Class Relationships.
§15.10	Template Instantiation.
§15.11	Implications of Templates.

“A C++ parameterized type will be referred to as a class template. A class template specifies how individual classes can be constructed much like the way a class specifies how individual objects can be constructed. A vector class template might be declared like this:

Click here to view code image

template<class T> class vector {
    T* v;
    int sz;
public:
    vector(int);
    T& operator[](int);
    T& elem(int i) { return v[i]; }
    // ...
};

The template <classT> prefix specifies that a template is being declared and that an argument T of type type will be used in the declaration. After its introduction, T is used exactly like other type names within the scope of the template declaration. Vectors can then be used like this:

Click here to view code image

vector<int> v1(20);
vector<complex> v2(30);

typedef vector<complex> cvec;  // make cvec a synonym
                               // for vector<complex>.
cvec v3(40); // v2 and v3 are of the same type.

void f()
{
    v1[3] = 7;
    v2[3] = v3.elem(4) = complex(7,8);
}

Clearly class templates are no harder to use than classes. The complete names of instances of a class template, such as vector<int> and vector<complex>, are quite readable. They might even be considered more readable than the notation for the built-in array type: int [] and complex []. When the full name is considered too long, abbreviations can be introduced using typedef.

It is only trivially more complicated to declare a class template than it is to declare a class. The keyword class is used to indicate arguments of type type partly because it appears to be an appropriate word, partly because it saves introducing a new keyword. In this context, class means “any type” and not just “some user-defined type.”

The <... > brackets are used in preference to the parentheses (...) to emphasize the different nature of template arguments (they will be evaluated at compile time) and because parentheses are already hopelessly overused in C++.

The keyword template is introduced to make template declarations easy to find, for humans and for tools, and to provide a common syntax for class templates and function templates.”

Templates provide a mechanism for generating types. They are not themselves types and have no run-time representation. Therefore, they have no effect on the object layout model.

One reason for the emphasis on run-time efficiency comparable to macros was that I wanted templates to be efficient enough in time and space to be used for low-level types such as arrays and lists. For that, I considered inlining essential. In particular, I saw standard array and vector templates as the only realistic way to allow C’s low-level array concept to be confined to the guts of implementations where it serves well. Higher-level alternatives – say, a range-checked array with a size() operation, a multidimensional array, a vector type with proper numeric vector operations and copy semantics, etc. – would be accepted by users only if their run-time, space, and notational convenience approached those of built-in arrays.

In other words, the language mechanism supplying parameterized types should be such that a concerned user should be able to afford to eliminate the use of arrays in favor of a standard library class (§8.5). Naturally, built-in arrays would still be there for people who wanted them and for the millions of lines of old code that use them. However, I intended to provide an efficient alternative to people who value convenience and type safety over compatibility.

Also, C++ supports virtual functions and through them a variant of every concept for which the obvious implementation technique is a jump table. For example, a “truly abstract” set of T would be implemented as a template that was an abstract class with its virtual functions operating on T objects (§13.2.2). For this reason, I felt I could concentrate on source-text-based, compile-time intensive solutions that provided near optimal run-time and space performance.

Click here to view code image

template<class T, int i> class Buffer {
    T v[i];
    int sz;
public:
    Buffer() :sz(i) {}
    // ...
};

Such templates are important when competing head on with C arrays and structs where run-time efficiency and compactness are important. Passing a size allows the implementer of a container to avoid free store use.

Had non-type arguments not been available, users would have encoded sizes in array types. For example:

Click here to view code image

template<class T, class A> class Buf {
    A v;
    int sz;
public:
    Buf() :sz(sizeof(A)/sizeof(T)) {}
    // ...
};

Buf<int,int[700]> b;

This seemed indirect, error-prone, and doesn’t extend cleanly to types other than integers. In particular, I wanted pointer to function template arguments for flexibility.

In the original template design, namespaces and templates could not be template arguments. This restriction was another case of simple caution. I now see no reason prohibit such arguments and they would obviously be useful. Class templates as template arguments were approved at the March 1994 meeting in San Diego.

““Should a user be required to specify the set of operations that may be used for a template argument of type type?” For example:

Click here to view code image

    // The operations =, ==, <, and <=
    // must be defined for an argument type T

template <
    class T {
        T& operator=(const T&);
        int operator==(const T&, const T&);
        int operator<=(const T&, const T&);
        int operator<(const T&, const T&);
    };
>
class vector {
    // ...
};

No. Requiring the user to provide such information decreases the flexibility of the parameterization facility without easing the implementation or increasing the safety of the facility. ... It has been argued that it is easier to read and understand parameterized types when the full set of operations on a type parameter is specified. I see two problems with this: such lists would often be long enough to be unreadable and a higher number of templates would be needed for many applications.”

In retrospect, I underestimated the importance of constraints in readability and early error detection, but I also discovered further problems with expressing constraints: a function type is too specific to be an effective constraint. If taken literally, a function type seriously overconstrains the solution. In the vector example, one would imagine that any < accepting two arguments of type T should be acceptable. However, in addition to the built-in operator < we have several plausible alternatives:

Click here to view code image

int X::operator<(X);
int Y::operator<(const Y&);
int operator<(Z, Z);
int operator<(const ZZ&,const ZZ&) ;

If taken literally, only ZZ would be an acceptable argument vector.

The idea of constraining templates repeatedly surfaced:

– Some people thought that better code could be generated if template arguments were constrained -1 don’t believe that.

– Some people thought static type checking was compromised by the absence of constraints – it isn’t, but some parts of static type checking are postponed until link time and that is indeed a practical problem.

– Some people thought that template declarations would be easier to understand given constraints – often, that is indeed the case.

The following sections present two alternative ways of expressing constraints. Generating member functions only if actually needed (§15.5) and specialization (§15.10.3) are alternatives to constraints in some cases.

Click here to view code image

template <class T> class Comparable {
    T& operator=(const T&);
    int operator==(const T&, const T&);
    int operator<=(const T&, const T&);
    int operator<(const T&, const T&);
};

template <class T : Comparable>
    class vector {
        // ...
    };

This makes sense. The various proposals differ in details, but they would all have the desired effect of pushing error detection and reporting forward to the compilation of an individual compilation unit. Proposals along this line are still under discussion in the C++ standards groups.

I do, however, have a fundamental objection to expressing constraints through derivation. It would encourage programmers to organize their programs so that anything that is a reasonable constraint is a class and thus encourage the use of inheritance to express every constraint. For example, instead of saying “T must have a less-than function,” one must say “T must be derived from Comparable.” This is an indirect and somewhat inflexible way of expressing constraints and can easily lead to an overuse of inheritance.

Because there are no inheritance relationships among built-in types, such as int and double, derivation cannot be used to constrain such types. Similarly, derivation cannot be used to express constraints that apply to both a user-defined and a built-in type. For example, the reasons that an int and a complex are often acceptable alternatives as template arguments cannot be expressed through derivation.

Further, a template writer can’t foresee every possible use of a template. This leads to programmers initially overconstraining template arguments, and then later – out of experience – underconstraining them. The logical outcome of constraints-through-derivation is the introduction of a universal base class to express “no constraints.” However, such a base class would become the cause of much sloppy coding both within the context of templates and elsewhere (see §14.2.3).

Using derivation to constrain template arguments also fails to address what has been discovered to be a nuisance: Derivation constraints do not allow a programmer to write two templates with the same name so that one is used for pointer types and the other for non-pointer types. This problem was first brought to my attention by Keith Gorlen. It can be addressed through template function overloading (§15.6.3.1).

A more fundamental criticism of this approach is that it uses inheritance for something that isn’t primarily sub-typing. I see constraints expressed in terms of inheritance as an example of inheritance being used just because it is fashionable rather than for any fundamental reason. Inheritance relationships are not the only useful relationships, and not all relationships between types and statements about types should be shoehorned into an inheritance framework.

Click here to view code image

template<class T> class X {
    // ...
    void constraints(T* tp)
    {                // T must have:
        B* bp = tp;  //   an accessible base B
        tp->f();     //   a member function f
        T a(l);      //   a constructor from int
        a = *tp;     //   assignment
        // ...
    }
};

Unfortunately, this takes advantage of a local implementation detail: Cfront does a complete syntax and semantic check of all inline functions when a template declaration is instantiated. However, a version of a function shouldn’t be generated for a particular set of template arguments unless it is called (§15.5).

The approach allows the template writer to specify a constraint function and a template user can check the constraint by calling the function when such a check is convenient for the user.

If the template writer does not want to bother the user, the template writer can call constraints() from every constructor. However, this can be tedious when there are many constructors and when those constructors wouldn’t ordinarily be inline.

If necessary, the notion could be formalized as a language feature:

Click here to view code image

template<class T>
    constraints {
        T* tp;       // T must have:
        B* bp = tp;  //   an accessible base B
        tp->f ();    //   a member function f
        T a(l);      //   a constructor from int
        a = *tp;     //   assignment
        // ...
    }
    class X {
        // ...
    };

This would allow constraints on template arguments for function templates, but I doubt this extension would be worthwhile. It is, however, the only constraint system I have seen that comes close to satisfying my desire not to overconstrain template arguments while remaining fully general, reasonably terse, comprehensible, and trivial to implement.

See §15.9.1 and §15.9.2 for examples of essential constraints expressed through use in template functions.

“Among other things, derivation (inheritance) ensures code sharing among different types (the code for a non-virtual base class function is shared among its derived classes). Different instances of a template do not share code unless some clever compilation strategy has been employed. I see no hope for having such cleverness available soon. So, can derivation be used to reduce the problem of code replicated because templates are used? This would involve deriving a template from an ordinary class. For example [Stroustrup,1988b]:

Click here to view code image

Click here to view code image

template<class T> class vector { // general vector type
    T* v;
    int sz;
public:
    vector(int);
    T& elem(int i) { return v[i]; }
    T& operator[](int i);
    // ...
};

template<class T> class pvector : vector<void*> {
        // build all vector of pointers
        // based on vector<void*>
public:
    pvector(int i) : vector<void*>(i) {}
    T*& elem(int i)
        { return (T*&) vector<void*>::elem(i); }
    T*& operator[](int i)
        { return (T*&) vector<void*>::operator[](i); }
    // ...
};

pvector<int*> pivec(100);
pvector<complex*> icmpvec(200);
pvector<char*> pcvec(300);

The implementations of the three vector of pointer classes will be completely shared. They are all implemented exclusively through derivation and inline expansion relying on the implementation of vector<void*>. The vector<void*> implementation is a good candidate for a standard library.”

This technique proved successful in curbing code bloat in real use. People who do not use a technique like this (in C++ or in other languages with similar facilities for type parameterization) have found that replicated code can cost megabytes of code space even in moderate size programs.

Addressing the same concern, I considered it essential to allow an implementation to instantiate only the template functions actually used. For example, given a template T with member functions f and g, an implementation should be allowed to instantiate only f if g isn’t used for a given template argument.

I also felt that generating versions of a template function for a given set of template arguments only if that function was called added an important degree of flexibility [Stroustrup, 1988b]:

“Consider vector<T>;. To provide a sort operation one must require that type T has some order relation. This is not the case for all types. If the set of operations on T must be specified in the declaration of vector one would have to have two vector types: one for objects of types with an ordering relation and another for types without one. If the set of operations on T need not be specified in the declaration of vector one can have a single vector type. Naturally, one still cannot sort a vector of objects of a type glob that does not have an order relation. If that is tried, the generated sort function vector<glob>::sort() would be rejected by the compiler.”

Click here to view code image

Click here to view code image

// declaration of a template function:
template<class T> void sort(vector<T>&);

void f(vector<int>& vi, vector<String>& vs)
{
    sort(vi);   // sort(vector<int>& v);
    sort(vs);   // sort(vector<String>& v);
}

// definition of a template function:
template<class T> void sort(vector<T>& v)
/*
    Sort the elements into increasing order

    Algorithm: bubble sort (inefficient and obvious)
*/
{
    unsigned int n = v.size();

    for (int i=0; i<n-l; i++)
        for (int j=n-l; i<j ; j--)
            if (v[j] < v[j-l]) { // swap v[j] and v[j-l]
                T temp = v[j];
                v[j] = v[j-l];
                v[j-l] = temp;
            }
}

As expected, function templates proved extremely useful in their own right, and they also proved essential for supporting class templates when non-member functions are preferred over member functions for providing services (for example, friends; §3.6.1).

The following subsections examine technical details related to template functions.

Click here to view code image

template<class T, int i>
    T lookup(Buffer<T,i>& b, const char* p);

int f(Buffer<int,128>& buf, const char* p) {

    return lookup (buf, p) ; // use the lookup() where
                             // T is int and i is 128
}

The answer used to be no because non-type arguments couldn’t be deduced. This was a real problem because it meant that one couldn’t define non-inlined non-member functions operating on a template class that took a non-type template argument. For example:

Click here to view code image

template<class T, int i> class Buffer {
    friend T lookup(Buffer&, const char*);
    // ...
};

requires a previously illegal template function definition.

The revised list of acceptable constructs in a template function argument list is:

Click here to view code image

T
const T
volatile T
T*
T&
T[n]
some_type [I]
CT<T>
CT<I>
T (*)(args)
some_type (*) (args_containing_T)
some_type (*) (args_containing_I)
T C:: *
C T:: *

Here, T is a template type argument, I is a template non-type argument, C is a class name, CT is the name of a previously declared class template, and args_containing_T is an argument list from which T can be determined by application of these rules. This makes the lookup() example legal. Fortunately, users need not memorize this list because it simply formalizes the obvious deductions.

Another example is:

Click here to view code image

template<class T, class U> void f(const T*, U(*)(U));

int g(int);

void h(const char* p)
{
    f(p,g); // T is char, U is int
    f(p,h); // error: can't deduce U
}

Looking at the arguments of the first call of f(), we easily deduce the template arguments. Looking at the second call of f(), we see that h() doesn’t match the pattern U (*) (U) because h()’s argument and return type differ.

John Spicer helped clarify this and many other similar issues.

Click here to view code image

vector<int> v(10); // class, template argument 'int'
sort<int>(v);      // function, template argument 'int'

However, I rejected the idea because explicit specification of template arguments wasn’t needed for most examples. I also feared “obscurity” and parsing problems. For example, how would we parse this example?:

Click here to view code image

void g()
{
    f<1>(0); // (f) < (1>(0)) or (f<1>) (0) ?
}

I now don’t consider this a problem. If f is a template name, f < is the beginning of a qualified template name and the subsequent tokens must be interpreted based on that; if not, < means less-than.

One reason explicit specification is useful is that we can’t deduce a return type from a call of a template function:

Click here to view code image

template<class T, class U> T convert(U u) { return u; }

Click here to view code image

void g(int i)
{
    convert(i);               // error: can't deduce T.
    convert<double>(i);       // T is double, U is int.
    convert<char,double>(i);  // T is char, U is double.
    convert<char*,double>(i); // T is char*, U is double
                              // error: cannot convert
                              // a double to a char*.
}

As for default function arguments, only trailing arguments can be left out of a list of explicit template arguments.

Explicit specification of template arguments allows the definition of families of conversion functions and object creation functions. An explicit conversion that performs what can be done by implicit conversion only, such as convert() is frequently requested and a good candidate for a library. Another variant would apply a check to ensure that narrowing conversions would cause a run-time error (§14.3.5.2).

The syntax for the new cast operators (§14.3) and for explicitly qualified template function calls were chosen to match. The new casts express operations that cannot be specified using other language features. Similar operations, such as convert() can be expressed as template functions, so they need not be built-in operators.

Another use of explicitly specified function template arguments is to control the algorithm used by specifying the type or value of a local variable. For example:

Click here to view code image

template<class TT, class AT> void f(AT a)
{
    TT temp = a;   // use TT to control
                   // precision of computation
    // ...
}

void g(Array<float>& a)
{
    f<float>(a);
    f<double>(a);
    f<Quad>(a);
}

Explicit specification of function template arguments was voted into C++ at the November 1993 San Jose meeting.

“Overloading resolution for template functions and other functions of the same name is done in three steps [ARM]:

[1] Look for an exact match [ARM,§13.2] on functions; if found, call it.

[2] Look for a function template from which a function that can be called with an exact match can be generated; if found, call it.

[3] Try ordinary overloading resolution [ARM,§13.2] for the functions; if a function is found, call it.

If no match is found, the call is an error. In each case, if there is more than one alternative in the first step that finds a match, the call is ambiguous and is an error.”

In retrospect, this seems too restrictive and too special purpose. Though it works, it opens the door for many minor surprises and annoyances.

Even at the time, it was clear that the best solution was somehow to unify the rules for ordinary and template functions; I just didn’t know how. Here is an outline of an alternative approach in a formulation suggested by Andrew Koenig:

“For a call, find the set of functions that could possibly be called; this will in general include functions generated from different templates. Apply the usual overload resolution rules to this set of functions.”

This would allow for conversions to be applied to template function arguments and provide a common framework for all function overloading. For example:

Click here to view code image

template<class T> class B { /* ... */ };
template<class T> class D : public B<T> { /* ... */ };

template<class T> void f(B<T>*);

void g(B<int>* pb, D<int>* pd)
{
    f(pb);  // f<int>(pb)
    f(pd);  // f<int>((B<int>*)pd); standard conversion used
}

This is necessary to make template functions interact properly with inheritance. Also:

Click here to view code image

template<class T> T max(T,T);

const int s = 7;


void k()
{
    max(s,7); // max(int(s), 7); trivial conversion used
}

The need to relax the rule against all conversions for template function arguments was anticipated in the ARM and many implementations currently allow the examples above. This issue remains to be formally resolved, though.

“Consider providing a print function for a vector type that sorts the elements before printing if and only if sorting is possible. A facility for inquiring if a certain operation, such as <, can be performed on objects of a given type can be provided. For example:

Click here to view code image

template<class T> void vector<T>::print()
{
    // if T has a < operation sort before printing

    if (?T::operator<) sort();
    for (int i=0; i<sz; i++) { /* ... */ }
}

Printing a vector of elements that can be compared will involve a sort() whereas printing a vector of elements that cannot be compared will not.”

I decided against providing this kind of type inquiry facility because I was – as I still am – convinced that it would lead to ill-structured code. In some ways, this technique combines the worst aspects of macro hackery and overreliance of type inquiries (§14.2.3).

Instead, specialization can be used to provide separate versions for specific template argument types (§15.10.3). Alternatively, operations that cannot be guaranteed for every template argument type can be isolated in separate member functions called only for types that actually have those operations (§15.5). Finally, template function overloading can be used to provide different implementations for different types. For example, let me show a reverse() template function that can reverse the order of elements in a container given iterators identifying the first and last element to be considered. User code should look like this:

Click here to view code image

void f(Listlter<int> 11, Listlter<int> 12, int* p1, int* p2)
{
    reverse(pi,p2);
    reverse(11,12);
}

where a ListIterator can be used to access elements from some user-defined container and an int* can be used to access an ordinary array of integers. To do that, different implementations of reverse() must somehow be selected for the two calls.

The reverse() template function simply chooses an implementation based on its argument type:

Click here to view code image

template <class Iter>
inline void reverse(Iter first, Iter last)
{
    rev(first,last,IterType(first));
}

Overload resolution is used to select IterTypes:

Click here to view code image

class RandomAccess { };

template <class T> inline RandomAccess IterType(T*)
{
    return RandomAccess();
}

class Forward { };

template <class T> inline Forward IterType(ListIterator<T>)
{
    return Forward();
}

Here, the int* will choose the RandomAccess and Listlter will choose the Forward. In turn, these iterator types will determine the version of rev() used:

Click here to view code image

template <class Iter>
inline void rev(Iter first, Iter last, Forward)
{
    // ...
}

template <class Iter>
inline void rev(Iter first, Iter last, RandomAccess)
{
    // ...
}

Note, that the third argument isn’t actually used in rev(); it is simply an aid to the overloading mechanism.

The fundamental observation is that every property of a type or an algorithm can be represented by a type (possibly defined specifically to do exactly that). That done, such a type can be used to guide the overload resolution to select a function that depends on the desired property. Unless the type used to select represents a fundamental property, this technique is a bit indirect, but very general and effective.

Please note that thanks to inlining this resolution is done at compile time, so the appropriate rev() function will be called directly without any run-time overhead. Note also that this mechanism is extensible in that new implementations of rev() can be added without touching old code. This example is based on ideas from Alex Stepanov [Stepanov, 1993].

If all other alternatives fail, run-time type identification can sometimes help (§14.2.5).

class vector<class T> {
    // ...
};

However, this didn’t cleanly extend to function templates [Stroustrup, 1988b]:

“The function syntax at first glance also looks nicer without the extra keyword:

Click here to view code image

T& index<class T>(vector<T>& v, int i) { /* ... */ }

There is typically no parallel (to class templates) in the usage, though, since function template arguments are not usually specified explicitly:

int i = index(vi,10);
char* p = index(vpc,29);

However, there appear to be nagging problems with this “simpler” syntax. It is too clever. It is relatively hard to spot a template declaration in a program because the template arguments are deeply embedded in the syntax of functions and classes and the parsing of some function templates is a minor nightmare. It is possible to write a C++ parser that handles function template declarations where a template argument is used before it is defined, as in index() above. I know, because I wrote one, but it is not easy nor does the problem appear amenable to traditional parsing techniques. In retrospect, I think that not using a keyword and not requiring a template argument to be declared before it is used would result in a set of problems similar to those arising from the clever and convoluted C and C++ declarator syntax.”

Using the final template syntax the declaration of index() becomes:

Click here to view code image

template<class T> T& index(vector<T>& v, int i) { /* ... */ }

At the time, I seriously discussed the possibility of providing a syntax that allowed the return value of a function to be placed after the arguments. For example

Click here to view code image

index<class T>(vector<T>& v, int i) return T& { /* ... */ }

or

Click here to view code image

index<class T>(vector<T>& v, int i) : T& {/*...*/ }

This would solve the parsing problem, but most people like having a keyword to help recognize templates, so that line of reasoning became redundant.

The <... > brackets were chosen in preference to parentheses because users found them easier to read and because parentheses are overused in the C and C++ grammar. As it happens, Tom Pennello proved that parentheses would have been easier to parse, but that doesn’t change the key observation that (human) readers prefer <... >.

One problem is a consistent nuisance:

List<List<int>> a;

appears to declare a list of a list of integers. In fact, it is a syntax error because the token >> (right shift or output) isn’t the same as the two tokens > >. Naturally, a simple lexical trick could solve this problem, but I decided to keep both the grammar and the lexical analyzer clean. I have now seen this mistake so often and heard so many complaints about

List<List<int>> a;

that I am sorely tempted to apply some glorious hack to make the problem go away. I find it more painful to listen to complaints from users than to listen to complaints from language lawyers.

Click here to view code image

template<class T> class List { /* ... */ };

List<int> 1i;
List< List<int> > 11i;
List< List< List<int> > > 111i;

If specific “composed types” are needed, they can be specifically defined using derivation:

Click here to view code image

template<class T> class List2 : public List< List<T> > { };
template<class T> class List3 : public List2< List<T> > { };

List2<int> 11i2;
List3<int> 111i3;

This is a somewhat unusual use of derivation because no members are added. No overhead in time or space is implied by this use of derivation; it is simply a composition technique. Had derivation not been available for composition, templates would have had to be augmented with specific composition mechanisms, or the language would have been much poorer. The smooth interaction between derivation and templates has been a continuous source of pleasant surprises to me.

Variables of such composed types can be used like their explicitly defined types, but not vice versa:

void f()
{
    11i = 11i2; // ok
    11i2 = 11i; // error
}

The reason is that public derivation defines a subtype relationship.

Allowing assignment in both directions would require a language extension to allow the introduction of genuine parameterized synonyms. For example:

Click here to view code image

template<class T> typedef List< List<T> > List4;

void (List< List<T> >& 1st1, List4& 1st2)
{

    1st1 = 1st2;
    1st2 = 1st1;
}

The extension is technically trivial, but I’m not sure how wise it would be to introduce yet another renaming feature.

Derivation also allows for partial specification of template arguments in the definition of a new type:

Click here to view code image

template<class U, class V> class X { /* ... */ };
template<class U> class XX : public X<U,int> { };

In general, deriving from a template class gives you the opportunity to tailor the base with information to suit the derived class. This allows for extremely powerful patterns of composition. For example:

Click here to view code image

template<class T> class Base { /* ... */ };

class Derived : public Base<Derived> { /* ... */ };

Such techniques make it possible for information about a derived class to flow into the definition of its base class. See also §14.2.7.

“One way is to use a template to compose a new class out of the interface to the desired container and an allocator class using the placement technique described in [2nd,§6.7.2]:

Click here to view code image

template<class T, class A> class Controlled_container
    : public Container<T>, private A {
   
    // ...
    void some_function()
    {
        // ...
        T* p = new(A::operator new(sizeof(T))) T;
       // ...
    }
    // ...
};

Here, it is necessary to use a template because we are designing a container. Derivation from Container is needed to allow a Controlled_container to be used as a container. The use of the template argument A is necessary to allow a variety of allocators to be used. For example:

Click here to view code image

class Shared : public Arena { /* ... */ };
class Fast_allocator { /* ...*/ };
class Persistent : public Arena { /* ... */ };

Controlled_container<Process_descriptor, Shared> ptb1;

Controlled_container<Node,Fast_allocator> tree;

Controlled_container<Personnel_record,Persistent> payroll;

This is a general strategy for providing nontrivial implementation information for a derived class. It has the advantage of being systematic and allowing inlining to be used. It does tend to lead to extraordinarily long names, though. As usual, typedef can be used to introduce synonyms for type names of undesirable length.”

The Booch components [Booch,1993] uses such composition techniques extensively.

We can’t hardwire the sorting criteria into the container^ because the container can’t (in general) impose its needs on the element types. We Can’t hardwire the sorting criteria into the element type because there are many different ways of sorting elements.

Consequently, the sorting criteria are neither built into the container nor into the element type. Instead, the criteria are supplied when a specific operation needs to be performed. For example, given strings of characters representing names of Swedes, what collating criteria would I like to use for a comparison? Two different collating sequences are in common use for sorting Swedish names. Naturally, neither a general string type nor a general sorting algorithm should have to know about the conventions for sorting names in Sweden.

Consequently, any general solution involves the sorting algorithm expressed in general terms that can be defined not just for a specific type but for a specific use of a specific type. For example, let us generalize the standard library function strcmp() for strings of any type T.

First, I define a class template giving the default meaning of comparison of objects of a type T:

Click here to view code image

template<class T> class CMP {
public:
    static int eq(T a, T b) { return a==b; }
    static int 1t(T a, T b) { return a<b; }
};

The template function compare() uses this form of comparison by default to compare basic_strings:

Click here to view code image

template<class T> class basic_string {
    // ...
};

template<class T, class C = CMP<T> >
int compare(const basic_string<T>& str1,
        const basic_string<T>& str2)
{
    for(int i=0; i<str1.length() && i< str2.length(); i++)
        if (!C::eq(str1[i],str2[i]))
            return C::1t(str1[i],str2[i]);
    return str2.length()-str1.length();
}

typedef basic_string<char> string;

Given member templates (§15.9.3), compare() could alternatively be defined as a member of basic_string.

If someone wants a C<T> to ignore case, to reflect locale, to return the largest of the Unicode values of the two elements that compared ! C<T>::eq(), etc., that can be done by defining suitable C<T>::eq() and C<T>::1t() in terms of operators “native” to T. This allows any (comparison, sorting, etc.) algorithm that can be described in terms of the operations supplied by CMP and the container to be expressed. For example:

Click here to view code image

class LITERATE {
    static int eq(char a, char b) { return a==b; }
    static int 1t(char,char); // use literary convention
};

void f(string swedel, string swede2)
{
    compare(swede1,swede2); // ordinary/telephone order
    compare<char,LITERATE>(swede1,swede2); // literary order
}

I pass the comparison criteria as a template parameter because that’s a way of passing several operations without imposing a run-time cost. In particular, the comparison operators eq() and 1t() are trivial to inline. I use a default argument to avoid imposing a notational cost on everyone. Other variants of this technique can be found in [2nd,§8.4].

A less esoteric example (for non-swedes) is comparing with and without taking case into account:

Click here to view code image

void f(string s1, string s2)
{
    compare(s1,s2); // case sensitive
    compare<char,NOCASE>(s1,s2); // not sensitive to case
}

Note that the CMP template class is never used to define objects; its members are all static and public. It therefore ought to be a namespace (§17):

Click here to view code image

template<class T> namespace CMP {
    int eq(T a, T b) { return a==b; }
    int 1t(T a, T b) { return a<b; }
}

Unfortunately, namespace templates are not (yet) part of C++.

As far as the C++ language rules are concerned, there is no relationship between two classes generated from a single class template. For example:

Click here to view code image

template<class T> class Set { /* ... */ };

class Shape { /* ... */ };
class Circle : public Shape { /* ... */ };

Given these declarations, people sometimes want to treat a Set<Circle> as a Set<Shape> or to treat a Set<Circle*> to be a Set<Shape*>. For example:

void f(Set<Shape>&);

void g(Set<Circle>& s)
{
    f (s);
}

This won’t compile because there is no built-in conversion from Set<Circle>& to Set<Shape>&. Nor should there be; thinking of Set<Circle> as a Set<Shape> is a fundamental – and not uncommon – conceptual error. In particular, Set<Circle> guarantees that its members are Circles, so that users can safely and efficiently apply Circle-specific operations, such as determining the radius, on its members. If we allowed a Set<Circle> to be treated as a Set<Shape>, we could no longer maintain that guarantee because it is presumably acceptable to put arbitrary Shapes such as Triangles into a Set<Shape>.

Click here to view code image

template<class T> class Ptr { // pointer to T
    // ...
};

we would often like to provide the inheritance relationships we are accustomed to for built-in pointers for these user-defined Ptrs. For example:

Click here to view code image

void f(Ptr<Circle> pc)
{
    Ptr<Shape> ps = pc; // can this be made to work?
}

We would like to allow this if and only if Shape really is a direct or indirect public base class of Circle. In particular, David Jordan asked the standards committee for that property for smart pointers on behalf of a consortium of Object-Oriented database suppliers.

Member templates – which are not currently part of C++ – provide a solution:

Click here to view code image

template<class Tl> class Ptr { // pointer to T1
    // ...
    template<class T2> operator Ptr<T2> ();
};

We need to define the conversion operator so that the Ptr<T1> to Ptr<T2> conversion is accepted if and only if a T1* can be assigned to a T2*. This can be done by providing Ptr with an extra constructor:

Click here to view code image

template<class T> class Ptr { // pointer to T
    T* p;
public:
    Ptr(T*);
    template<class T2> operator Ptr<T2> () {
        return Ptr<T2>(p); // works iff p can be
                           // converted to a T2*
    }
    // ...
};

This solution has the nice property that it doesn’t use any casts. The return statement will compile if and only if p can be an argument to Ptr<T2>’s constructor. Now, p is a T1* and the constructor expects a T2* argument. This is a subtle application of the constraints through use technique (§15.4.2). If you prefer to keep the extra constructor private, you can use a technique suggested by Jonathan Shopiro:

Click here to view code image

template<class T> class Ptr { // pointer to T
    T*  tp;
    Ptr(T*);
    friend template<class T2> class Ptr<T2>;
public:
    template<class T2> operator Ptr<T2> ();
    // ...
};

Member templates are described in §15.9.3.

Click here to view code image

template<class scalar> class complex {
    scalar re, im;
public:
    // ...
};

Given that we can use complexe<float>, complex<double>, etc. However, when doing that, we would like to convert from a complex with lower precision to one with higher precision. For example:

Click here to view code image

complex<double> sqrt(complex<double>);

complex<float> cl(1.2f,6.7f);
complex<double> c2 = sqrt(cl); // error, type mismatch:
                               // complex<double> expected

We would like a way of making the call of sqrt legal. This leads programmers to abandon the template approach to complex in favor of replicated class definitions:

Click here to view code image

class float_complex {
    float re, im;
public:
    // ...
};

class double_complex {
    double re, im;
public:
    double_complex(float_complex c) :re(c.re), im(c.im) {}
    // ...
};

The purpose of the replication is to define the constructor that defines the conversion.

Again, all solutions I can think of require the combination of nested templates and some form of constraints. Again, the actual constraint can be implicit:

Click here to view code image

template<class scalar> class complex {
    scalar re, im;
public:
    template<class T2> complex(const complex<T2>& c)
        : re(c.re), im(c.im) { }
    // ...
};

In other words, you can construct a complex<Tl> from a complex<T2> if and only if you can initialize a T1 by a T2. That seems reasonable. Interestingly enough, this definition subsumes the usual copy constructor.

This definition makes the sqrt() example above legal. Unfortunately, this definition also allows narrowing conversions of complex numbers simply because C++ allows narrowing conversions for scalars. Naturally, given this definition of complex, an implementation that warns against narrowing conversions of scalars will automatically also warn against narrowing conversions of complex values.

We can get the “traditional” names back by using typedef:

Click here to view code image

typedef complex<float> float_complex;
typedef complex<double> double_complex;
typedef complex<long double> long_double_complex;

Personally, I find the un-typedef’d versions more readable.

Click here to view code image

class Shape {
    // ...
    template<class T>
        virtual Bool intersect(const T&) const =0;
};

class Rectangle : public Shape {
    // ...
    template<class T>
        virtual Bool intersect(const T& s) const;
};

template<class T>
virtual Bool Rectangle::intersect(const T& s) const
{
    return s.intersect(*this); // *this is a Rectangle:
                               // resolve on s
}

This must be illegal, otherwise we would have to add another entry to the virtual table for class Shape each time someone called Shape::intersect() with a new argument type. This would imply that only the linker could make virtual function tables and assign table positions to functions. Consequently, a member template cannot be virtual.

I found this problem only after the publication of the ARM and was thus saved by the restriction that templates must be defined in the global scope. On the other hand, the conversion problems mentioned in §15.9 have no solution in the absence of member templates. Member templates were voted into C++ at the March 1994 meeting in San Diego.

Please note that explicit specification of template arguments for function templates is an alternative to nested template classes in many cases (§15.6.2).

The ARM comments on this problem without giving a definite answer:

“These rules imply that the decision of what functions to generate from function template definitions cannot be made until a program is complete, that is, not until it is known what function definitions are available.

As stated, error detection has been postponed to the last possible moment: the point after initial linking where definitions are generated for template functions. This is too late for many people’s tastes.

As stated, the rules also place the maximum reliance on the programming environment. It will be up to the system to find the definitions of the class templates, function templates, and classes needed for generating those template function definitions. This will be unacceptably complicated for some environments.

Both problems can be alleviated by the introduction of mechanisms allowing a programmer to say “generate these template functions here for these template arguments.” This can be made simple enough for any environment and will ensure that errors relating to a specific template function definition are detected on request.

It is not clear, however, whether such mechanisms should be considered part of the language or part of the programming environment. It was felt that more experience was needed and, for that reason, such mechanisms belonged in the environment – at least temporarily.

The simplest mechanism for ensuring proper generation of template function definitions is to leave the problem to the programmer. The linker will tell which definitions are needed, and a file containing non-inline template function definitions can be compiled together with an indication of which template arguments are to be used. More sophisticated systems can be built based on this fully manual base.”

Now, a variety of implementations are available. Experience shows that the problem was at least as hard as suspected and that something better than the existing implementations was needed.

The Cfront implementation [McCluskey,1992] automates template instantiation completely as suggested by the original template design [Stroustrup, 1988b] and the ARM. Basically, the linker is run, and if some template function instantiations are missing, the compiler is invoked to produce the missing object code from the template source. This process is repeated until all templates used have been instantiated. Template and argument-type definitions are (when needed) found based on a file naming convention. Where needed, this convention is supplemented by a user-supplied directory file that maps template and class names to the files that contain their definitions. The compiler has a special mode for processing template instantiations. This strategy often works very well, but in some contexts three very annoying problems were discovered:

[1] Poor compile- and link-time performance: Once a linker has determined that the instantiation is needed, the compiler has to be invoked to generate the needed functions. That done, the linker needs to be invoked again to link the new functions. In a system where the compiler and linker are not permanently running, this can be surprisingly costly. A good library mechanism can significantly reduce the number of times the compiler has to be run.

[2] Poor interaction with some source control systems: Some source control systems have very definite ideas about what source code is and how object code is produced from it. Such systems don’t interact well with a compilation system where the linker, the compiler, and a library interact to produce a complete program (in the way outlined in [1]). This is not a fault of the language, but that is no consolation to programmers who have to live with such a source-control system.

[3] Poor hiding of implementation details: If I use templates in the implementation of a library, then the source of those templates must be included with my library for a user to link my library. The reason is that the need to generate template instantiations will only be noticed at the final link time. This problem can only be bypassed by (somehow) producing object code that contains every version of the templates I use in my implementation. This can lead to object-code bloat as the implementer tries to cover every possible use – any one application will use only a subset of the possible template instantiations. Note also, that if the instantiation of implementation templates depends directly on which templates a user instantiates, late instantiation is necessary.

What would be the benefit of an optional instantiation operator?

[1] Users would be able to specify the environment for instantiation.

[2] Users would be able to pre-create libraries of common instantiations in a relatively implementation-independent manner.

[3] These pre-created libraries would be independent of changes in the environment of the program that used them (depending only on the context of instantiation).

The instantiation request mechanism described here was adopted at the San Jose meeting; it has its roots in a proposal by Erwin Unruh. The syntax was chosen to match the way template arguments are explicitly specified in uses of class templates (§15.3), template function calls (§15.6.2), the new cast operators (§14.2.2, §14.3), and template specializations (§15.10.3). An instantiation request looks like this:

Click here to view code image

template class vector<int>;                  // class
template int& vector<int>::operator[](int);  // member
template int convert<int,double>(double);    // function

The keyword template was recycled for this use in preference to introducing a new keyword instantiate. A template declaration is distinguished from an instantiation request by the template argument list: template< begins a template definition, whereas plain template begins an instantiation request. The fully specified form of the functions was chosen over possible abbreviated forms such as

Click here to view code image

   // not C++:

template vector<int>::operator[];  // member
template convert<int,double>;      // function

to avoid ambiguities for overloaded template functions, to provide the compiler with redundancy needed for consistency checks, and because instantiation requests are infrequent enough to cast doubt on the value of a terse notation. However, as in template function calls, the template arguments that can be deduced from the function arguments can be omitted (§ 15.6.1). For example:

Click here to view code image

template int convert<int>(double); // function

When a class template is explicitly instantiated, every member function presented to the compiler (§15.10.4) is also instantiated. This implies that an explicit instantiation can be used as a constraints check (§15.4.2).

The link-time and recompilation efficiency impact of instantiation requests can be significant. I have seen examples in which bundling all template instantiations into a single compilation unit cut the compile time from a number of hours to the equivalent number of minutes. For this magnitude of speedup, I am willing to accept a mechanism for manual optimization.

What should happen if a template is explicitly instantiated twice for the same set of template arguments? This question was (rightly, I think) considered critical. If that is an unconditional error, explicit instantiation becomes a serious obstacle to composition of programs out of separately developed parts. This was the original reason for not introducing an explicit instantiation operator. On the other hand, suppressing redundant explicit instantiations could in general be very difficult.

The committee decided to dodge the issue slightly by leaving some freedom to the implementers: Multiple instantiations is a nonrequired diagnostic. This allows a smart implementation to ignore redundant instantiations and thereby avoid the problems related to composition of programs from libraries using explicit instantiation mentioned above. However, the rule does not require implementations to be smart. Users of “less smart” implementations must avoid multiple instantiations, but the worst that will happen if they don’t is that their program won’t load; there will be no silent changes of meaning.

As ever, no explicit instantiation is required by the language. Explicit instantiation is a mechanism for manual optimization of the compile-and-link process.

The revised name binding rules described in this section are the result of work by many people over the last few years, notably members of the extensions working group, Andrew Koenig, Martin O’Riordan, Jonathan Shopiro, and me. By the time they were accepted (November 1993, San Jose) they had also benefited from significant implementation experience.

Consider this example:

Click here to view code image

Click here to view code image

#include<iostream.h>
#include<vector.h>

void db(double);
                                         // #1
template<class T> T sum(vector<T>& v)
{
    T t = 0;
    for (int i = 0; i<v.size(); i++) t = t + v [ i ];
    if (DEBUG) {
        cout << "sum is " << t << ' ';
        db(t);
        db(i);
    }
    return t;
}
// ...

#include<complex.h>
                                         // #2
void f(vector<complex>& v)
{
    complex c = sum(v);
}

The original definition says that names used in the template are all bound at the point of instantiation and that the point of instantiation is just before the global declaration in which a template is first used (#2 above). This has at least three undesirable properties:

[1] No error checking can be performed at the point of the template definition. For example, if DEBUG is undefined at that point, no error message can be produced.

[2] Names defined after the template definition can be found and used. This is often (but not always) a surprise to the reader of the template definition. For example, one might expect the call db (i) to be resolved to the db (double) declared above, but if the ... contains a declaration of db (int) then db (int) would be preferred over db (double) under the usual overload resolution rules. On the other hand, if a db (complex) is defined in complex. h, we need db (t) to resolve to db (complex) rather than being an error by not being a valid call of the db (double) visible from the template definition.

[3] The set of names available at the point of instantiation will differ when sum is used in two different compilations. If sum (vector<comp 1 ex>&) thereby gets two different definitions the resulting program is illegal under the one-definition rule (§2.5). However, the checking of the one-definition rule in such cases is beyond a traditional C++ implementation.

In addition, this original rule doesn’t explicitly cover the case where the definition of the template function isn’t included in this particular compilation unit. For example:

Click here to view code image

template<class T> T sum(vector<T>& v);

// ...

#include<complex.h>
                                         // #2
void f(vector<complex>& v)
{
    complex c = sum(v);
}

No guidance was given to implementers or users about how the definition of the sum () function templates was supposed to be found. In consequence, different implementers used different heuristics.

The general problem is that three contexts are involved in a template instantiation and they cannot be cleanly separated:

[1] The context of the template definition.

[2] The context of the argument type declaration.

[3] The context of the use of the template.

The overall aim of the template design is to assure that enough context is available for the template definition to make sense in terms of its actual arguments without picking up “accidental” stuff from the environment at the call point.

The original design relied exclusively on the one-definition rule (§2.5) to maintain sanity. The assumption was that if accidental stuff affected the definition of the generated function, it was most unlikely to happen consistently over all uses of a template function. This is a good assumption, but – for good reasons – implementations usually don’t check for inconsistencies. The net effect is that reasonable programs work. However, people who wish that templates were really macros can get away with writing programs that take advantage of the calling environment in undesirable (according to me) ways. Also, implementers have a major headache when they want to synthesize a context for a template definition to speed up instantiation.

Refining the definition of point of definition in such a way that it is both better than the original and doesn’t break reasonable programs was difficult, but necessary.

A first attempt would be to require every name used in the template to be defined at the point of the template definition. This would make the definition readable, guarantee that nothing undesirable was picked up accidentally, and allow perfect early error detection. Unfortunately, that wouldn’t allow the template to apply operations on objects of its template class. In the example above, +, f(), and the constructor for T are undefined at the point of the template definition. We can’t declare them in the template either because we can’t specify their types. For example, + may be a built-in operator, a member function, or a global function. If it is a function, it may take arguments of type T, const T&, etc. This is exactly the problem of specifying template argument constraints (§15.4).

Given that neither the point of the template definition nor the point of template use provides a good enough context for template instantiation, we must look for a solution that combines aspects of both.

The solution is to separate names used in a template definition into two categories:

– The ones that depend on a template argument.

– The ones that don’t.

The latter can be bound in the context of the template definition, the former in the context of an instantiation. This concept is clean to the extent that the definition of “depends on a template argument” can be made clean.

Click here to view code image

class complex {
    // ...
    friend complex operator+(complex,complex);
    complex(double);
};

For this to work, the definition “depends on a template argument T” must at least be extended to include T’s friends. However, even that isn’t enough because crucial nonmember functions don’t always need friendship:

Click here to view code image

class complex {
    // ...
    complex operator+=(complex);
    complex(double);
};

complex operator+(complex a, complex b)
{
    complex r = a;
    return r+=b;
}

It would also be unreasonable and constraining to require the designer of a class to provide all the functions that a writer of a template might possibly need in the future; 20/20 foresight is rare.

Consequently, “depends on a template argument T” must rely on the context of the point of instantiation to at least the extent of finding the global functions used for Ts. This will inevitably open the possibility of some unexpected function being used. However, that problem is minimized. We define “depends on a template argument T” in the most general way; that is, a function call depends on a template argument if the call would have a different resolution or no resolution if the actual template type were missing from the program. This condition is reasonably straightforward for a compiler to check. Examples of calls that depend on an argument type T are:

[1] The function called has a formal parameter that depends on T according to the type deduction rules (§15.6.1). For example: f (T), f (vector<T>), and f (const T*).

[2] The type of the actual argument depends on T according to the type deduction rules (§15.6.1). For example: f(T(1)), f(t), f(g(t)), and f(&t) assuming that t is a T.

[3] A call is resolved by the use of a conversion to T without either an actual argument or a formal argument of the called function being of a type that depended on T as specified in [1] and [2].

The last example was found in real code, and the code that relied on it seemed quite reasonable. A call f (1) didn’t look dependent on T, and neither did the function f (B) that it invoked. However, the template argument type T had a constructor from int and was derived from B, so the resolution of f (1) was f (B (T (1))).

These three kinds of dependencies exhaust the examples I have seen.

[1] Prefer lookup #1.

[2] Prefer lookup #2.

[3] Make it an error.

Note that lookup #1 can only be done for nonfunctions and for functions where the types of all arguments are known at the point of use in the template definition; the lookup of other names must be postponed to point #2.

Essentially, the original rule says “prefer lookup #2,” and this implies that the usual ambiguity resolution rules are applied because only if a better match was found by lookup #2 could it have found a different function from lookup #1. Unfortunately, this makes it very hard to trust what you see when you read the text of a template definition. For example:

Click here to view code image

double sqrt(double);

template<class T> void f(T t)
{
    double sq2 = sqrt(2);
    // ...
}

It seems obvious that sqrt (2) will call sqrt (double). However, there just might be a sqrt (int) found in lookup #2. In most cases, that wouldn’t matter because the “must depend on a template argument” rule would ensure that the “obvious” resolution to sqrt (double) would be used. However, if T was int then the call sqrt (2) would depend on the template argument, so the call would resolve to sqrt (int). This is an inescapable consequence of taking lookup #2 into account, but I considered it most confusing and would like to avoid it.

On the other hand, I thought it necessary to give preference to lookup #2 because only that could resolve uses of base class members as an ordinary class would have. For example:

Click here to view code image

void g();

template<class T> class X : public T {
    void f () { g() ; }
    // ...
};

If T has a g() then that g() ought to be called to match the way nontemplate classes behave:

Click here to view code image

void g();

class T { public: void g(); }

class Y : public T {
    void f() { g(); } // calls T::g
    // ...
};

On the other hand, in the usual “non-perverted” cases sticking with what was found in lookup #1 seems right. This is how lookup of global names is done in C++, this is what allows the largest amount of early error-detection, this is what allows the largest amount of pre-compilation of templates, and this is what provides the most protection against “accidental” hijacking of names by context unknown to the template writer. Over the years I have come to appreciate the importance of these matters and several implementers, notably Bill Gibbons, argued persuasively for preferring lookup #1.

For a while, I favored making it an error for different functions to be found in the two lookups, but that complicates matters for the implementers without giving significant benefits to the users. Also, this would allow names in the context of a use of a template to “break” otherwise good template code written by a programmer who intended names in scope at the point of the template definition to be used. Finally, after hours of work in the extensions working group, I changed my mind. The argument that clinched the case for preferring lookup #1 was that the really tricky examples can trivially be resolved by the template writer. For example:

Click here to view code image

double sqrt(double);

template<class T> void f(T t)
{
    // ...
    sqrt(2);      // resolve in lookup #1
    sqrt(T(2));   // clearly depends on T
                  // bind in lookup #2
    // ...
}

and:

Click here to view code image

int g();

template<class T> class X : public T {
    void f()
    {
        g();     // resolve in lookup #1
        T::g();  // clearly depends on T
                 // bind in lookup #2
    }
    // ...
};

Essentially, this requires the template writer to be more explicit when the intent is to use some function that isn’t actually visible from the template definition. That seems to put the burden in the right place and have the right default behavior.

Click here to view code image

template<class T> class Comparable {
    // ...
    int operator==(const T& a, const T& b) { return a==b; }
};

specifies that for every T, you compare elements with the == operator. Unfortunately, that is quite restrictive. In particular, C strings represented by char*s are usually better compared using strcmp().

During the initial design, we found that such examples abounded and that the “special cases” were often essential for generality or critical for performance reasons. C-style strings are a good example of this.

I therefore concluded that we needed a mechanism for “specializing” templates. This could be done either by accepting general overloading or by some more specific mechanism. I chose a specific mechanism because I thought I was primarily addressing irregularities caused by irregularities in C and because suggestions of overloading invariably creates a howl of protests. I was trying to be cautious and conservative; I now consider that a mistake. Specialization as originally defined was a restricted and anomalous form of overloading that fitted poorly with the rest of the language.

A class or function template can be “specialized.” For example, given a template

Click here to view code image

template<class T> class vector {
    // ...
    T& operator[](int i);
};

one can provide specializations, that is separate declarations, for, say vector<char> and vector<complex>::operator[](int):

Click here to view code image

class vector<char> {
    // ...
    char& operator[](int i);
};


complex& vector<complex> :: operator [] (int i) { /* ... */ }

This enables a programmer to provide specialized implementations for classes that are either particularly important from a performance point of view or have semantics that differ from the default. This mechanism is crude and very effective.

My original idea was that such specializations would be put into libraries and automatically used where necessary without programmer intervention. This proved a costly and questionable service. Specialization caused comprehension and implementation problems because there was no way of knowing what a template meant for a particular set of template arguments – even if we were looking at the template definition – because the template may have been specialized in some other compilation unit. For example:

Click here to view code image

template<class T> class X {
    T v;
public:
    T read() const { return v; }
    void write(int vv) { v=vv; }
};

void f(X<int> r)
{
    r.write(2);
    int i = r.read();
}

It would seem reasonable to assume that f() uses the member functions defined above. However, that was not guaranteed. Some other compilation unit may have defined X<int>::write() to do something completely different.

Specialization can also be considered as opening a protection loophole in C++ because a specialized member function can access a template class’ private data in a way that is not discernible from reading the template definition. There were even more technical problems.

I concluded that specialization as originally defined was a botch and also provided essential functionality. How might we provide the functionality while remedying the botch? After many complicated arguments, I proposed a trivially simple solution that was accepted at the San Jose meeting: A specialization must be declared before it is used. This simply brings specialization into line with the rules for ordinary overloading. If no specialization is in scope at a point of use, the general template definition will be used. For example:

Click here to view code image

Click here to view code image

template<class T> void sort(vector<T>& v)
    { /* ... */ }

void sort<char*>(vector<char*>& v);  // specialization

void f(vector<char*>& v1, vector<String>& v2)
{
    sort(v1); // use specialization
              // sort(vector<char*>&)

    sort(v2); // use general template
              // sort(vector<T>&), T is String
}

void sort<String>(vector<String>& v); // error: specialize
                                      // after use

void sorto(vector<double>& v); // fine: sort<double>
                               // hasn't yet been used

We considered an explicit keyword for requesting a specialization. For example:

Click here to view code image

specialise void sort(vector<String>&);

but the mood of the committee at the San Jose meeting was strongly against new keywords and I would never have managed to get agreement on the spelling of specialize vs. specialise in that thoroughly international gathering.

Templates don’t fit neatly into this picture. That is the root of many of the problems with template implementations. A template isn’t just source code (what is instantiated from a template is more like traditional source code), so template definitions don’t quite belong in . c files. On the other hand, templates are not just types and interface information, so they don’t quite belong in . h files either.

The ARM didn’t offer sufficient guidance to implementers (§15.10), and this has led to a proliferation of schemes that are becoming a barrier to portability. Some implementations have required templates to be placed in . h files. This can lead to performance problems because too much information is supplied for each compilation and because each compilation unit appears to depend on all the templates in its . h files. Basically, template function definitions don’t belong in header files. Other implementations have required template function definitions to be placed in . c files. This leads to problems with finding a template function definition when an instantiation is needed, and it also complicates the composition of a context for an instantiation.

I suspect that any solution to these problems must be based on the recognition that a C++ program is more than a set of unrelated separately compiled units. This is true even during compilation. Somehow, the concept of a central point where information related to templates and other issues that affect multiple compilation units must be recognized. Here I will call that point the repository because its role is to keep information that the compiler needs between compilations of the separate parts of a program.

Think of the repository as a persistent symbol table with one entry per template that the compiler uses to keep track of declarations, definitions, specializations, uses, etc. Given that concept, I can outline a model of instantiation that supports all language facilities, accommodates the current uses of . h and . c files, doesn’t require the user to know about the repository, and provides the alternatives for error checking, optimization, and compiler/linker efficiencies that implementers have asked for. Note that this is a model for an instantiation system, rather than a language rule or a specific implementation. Several alternative implementations are possible, but I suspect a user could ignore the details (most of the time) and think of the system this way.

Let me outline what might happen in a number of cases from the point of view of a compiler. As usual, . c files are fed to the compiler, and they contain #include directives for . h files. The compiler knows only about code that has been presented to it. That is, it never looks around in the file system to try to find a template definition that it hasn’t already been presented with. However, the compiler uses the repository to “remember” which templates it has seen and where they came from. This scheme can easily be extended to include the usual notions of archives. Here is a brief description of what a compiler does at critical points:

– A template declaration is seen: The template can now be used. Enter the template into the repository.

– A function template definition is seen in a . c file: The template is processed as far as necessary to enter it into the repository. If it is already entered, we give a double-definition error unless it is a new version of same template.

– A function template definition is seen in a . h file: The template is processed as far as necessary to enter it into the repository. If it is already entered, we check that the already-entered template did in fact originate in the same header. If not, we give a double-definition error. We check that the one-definition rule hasn’t been violated by checking that this definition is in fact identical to the previous one. If not, we give a double-definition error unless it is a new version of same template.

– A function template specialization declaration is seen: If necessary, give a used-before-specialized error. The specialization can now be used. Enter the declaration into the repository.

– A function template specialization definition is seen: If necessary, give a used-before-specialized error. The specialization can now be used. Enter the definition into the repository.

– A use is encountered: Enter the fact that the template has been used with this set of template arguments into the repository. Look into the repository to see if a general template or a specialization has been defined. If so, error checking and/or optimizations may be performed. If the template has not previously been used for this set of template arguments, code may be generated. Alternatively, code generation can be postponed until link time.

– An explicit instantiation request is encountered: Check if the template has been defined. If not, give a template-not-defined error. Check if a specialization has been defined. If so, give an instantiated-and-specialized error. Check if the template has already been instantiated for this set of template arguments. If so, a double-instantiation error may be given, or the instantiation request may be ignored. If not, code may be generated. Alternatively, code generation can be postponed until link time. In either case, code is generated for every template class member function presented to the compiler.

– The program is linked: Generate code for every template use for which code hasn’t already been generated. Repeat this process until all instantiations have been done. Give a use-but-not-defined error for any missing template functions.

Code generation for a template and a set of template arguments involves lookup #2 mentioned in §15.10.2. Naturally, checking against illegal uses, unacceptable over-loadings, etc., must also be performed.

An implementation can be more or less thorough in checking for violations of the one-definition rule and the rule against multiple instantiations. These are nonrequired diagnostics, so the exact behavior of the implementation is a quality-of-implementation issue.

In the absence of templates, there was no way in C++ to implement container classes without extensive use of casting and the manipulation of objects through pointers to common base classes or void*. In principle, this can all be eliminated. However, I suspect that misuses of inheritance stemming from misguided application of Smalltalk techniques in C++ (for example, see §14.2.3) and overuse of weakly typed techniques stemming from C will be very hard to root out.

On the other hand, I expect that it will be possible to slowly get rid of many of the unsafe practices involving arrays. The ANSI/ISO standard library has the dynarray template class (§8.5) so that people can use it or some “home brew” array template to minimize the unchecked uses of arrays. People often criticize C and C++ for not checking array bounds. Much of that criticism is misguided because people forget that just because you can make a range error on a C array, you don’t have to. Array templates allow us to relegate the low-level C arrays to the bowels of an implementation where they belong. Once the frequency of C-style array usage goes down and their use becomes more stylized within class and template implementations, the number of errors that can be attributed to C arrays will be drastically reduced. This has been slowly happening for years and templates, especially templates in libraries, accelerate this trend.

The third important aspect of templates is that they open completely new possibilities for library design when used for composition in combination with derivation (§15.8). In the long run, that might be the most important aspect.

Even though implementations supporting templates are no longer uncommon, they they are not yet universally available, either. Furthermore, most such implementations are at the time of writing immature. This currently limits the impact of templates on people’s thinking about C++ and the design of programs. The ANSI/ISO resolutions of the various dark corners ought to solve both problems so that we will see templates take the central place in the C++ programmer’s tool box that they were designed for.

Many people expressed concern that templates relied too heavily on the availability of source code. This was seen as having two bad side-effects:

[1] You can’t keep your implementation a trade secret.

[2] If a template implementation changes, user code must be recompiled.

This is certainly the case for the most obvious implementation, but the trick of deriving template classes from classes that provide a clean interface limits the impact of these problems. Often, a template simply provides interface code to something that can be “secret” and can be changed without affecting users. The pvector example from §15.5 is a simple example of that. A template version of the set example from §13.2.2 would be another. My view was that people who were concerned with these matters had an alternative in the virtual function concept and I needn’t provide another variant of the jump table.

It is also possible to devise a partially compiled form of templates that will keep the implementer’s secrets as safe – or maybe as unsafe – as ordinary object code.

To some, the problem is to ensure that no new versions of templates meant to be secret are instantiated – directly or indirectly – by the user. This can be ensured simply by not supplying their source. That approach is feasible if the supplier can preinstantiate (§15.10.1) all versions needed. Those versions (and only those) can then be shipped as object code libraries.

“C++ is a powerful enough language – the first such language in our experience – to allow the construction of generic programming components that combine mathematical precision, beauty, and abstractness with the efficiency of non-generic hand-crafted code.”

We have yet to discover the full power of the combination of templates, abstract classes, exception handling, etc. I don’t consider the factor-ten difference in the size of the Booch Ada and C++ components [Booch, 1993b] a freak example (§8.4.1).

When I first considered templates and also when I used them later, I found several cases in which built-in types were treated slightly differently than classes. This became an obstacle to writing templates that could be used with both classes and built-in type arguments. I therefore set out to ensure that minor syntactic and semantic details applied uniformly to all types. This effort continues to this day.

Consider:

Click here to view code image

vector v(10); // vector of 10 elements

This initializer syntax used to be illegal for built-in types. To allow it, I introduced the notion that built-in types have constructors and destructors. For example:

Click here to view code image

int a(1); // pre-2.1 error, now initializes a to 1

I considered extending this notion to allow derivation from built-in classes and explicit declaration of built-in operators for built-in types. However, I restrained myself.

Allowing derivation from an int doesn’t actually give a C++ programmer anything significantly new compared to having an int member. This is primarily because int doesn’t have any virtual functions for the derived class to override. More seriously though, the C conversion rules are so chaotic that pretending that int, short, etc., are well-behaved ordinary classes is not going to work. They are either C compatible or they obey the relatively well-behaved C++ rules for classes, but not both.

Allowing the definition of built-in operators such as operator+ (int, int) would also have made the language mutable. However, allowing such functions to be synthesized so that one could pass pointers to them and in other ways refer directly to them seems attractive.

Conceptually, built-in types do have constructors and destructors, though. For example:

Click here to view code image

template<class T> class X {
    T a;
    int i;
    complex c;
public:
    X() :a(T()), i(int()), c(complex()) { }
    // ...
};

The constructor for X initializes each of its members by calling the member’s default constructor. The default constructor for any type T is defined to yield the same value as a global variable of type T that hasn’t been explicitly initialized. This is an improvement over the ARM where X() is defined to yield an undefined value unless a default constructor is defined for X.