"Templates" are a feature of C++ which provide limited support for generic programming, even though it's an early-binding language. You might also consider templates a more powerful and convenient replacement for macros. In fact, we've just said the same thing in two different ways. "Let's have a look under the hood", as Ross Perot used to say before the lawn gnomes dragged him screaming and wiggling down to Hell and fed his tremulous midget heart to the Whipper-Choppers.

We'll start with a very simple example, min(). min() takes two arguments and returns the lesser of the two. This is how you might write it as an ordinary function:

    int min( int a, int b )
        return ( a < b ) ? a : b;

The problem there is that it won't work with any type other than int. You could write a double dblmin( double a, double b ) and a dozen others, but you'd spend a lot of time copying and pasting code, and the only thing that would change each time would be the types. The body of the function would never change. The C/C++ macro facility is a much better way to do it:

    [#define] min( a, b )   ( ( (a) < (b) ) ? (a) : (b) )

You'd "call" both the function and the macro in exactly the same way, but while the function would be an ordinary function call, the macro would be something else entirely: It would be expanded before the code is compiled. If you use our min() macro and then instruct your compiler to give you preprocessor output instead of compiling, you'll see something like this:

/* before */
    int a = min( foo(), 5 );

/* after */
    int a = ( ( (foo()) < (5) ) ? (foo()) : (5) );

The preprocessor just replaces a with whatever you give it for the first parameter, and b with whatever you give it for the second parameter. Macros just perform a search and replace on the source code before the compiler sees it. Note that a is a function call, and it gets called twice. That might be a very bad thing. Worse yet, it might only be a moderately bad thing (a harmful recessive, so to speak). This is only one of the reasons why macros are considered harmful by many programmers. Another is that the "invisible" changes in the source make life difficult when you use interactive debuggers or look at the errors and warnings generated by your compiler. The code that's being compiled bears an oftimes arbitrary resemblance to what's in the source file. The only great thing about macros is that they can let you reuse logic without investing in a function call, but as we've seen, you might be squandering hard-earned cycles on other redundant calls. Besides, C++ supports inline functions which do inline code, but put the arguments in temporaries. You can still use macros if your chest is that hairy. Once in a while, they're the Right Thing.

The purpose of templates is to let us have our cake and eat it. Here's a third min() implementation, the way George Jetson would write it. It's in C++ -- The Language of the Future!

    template <class T>
    inline T min( T a, T b )
        //  GCC prefers that you cast b to T1 here
        return ( a < b ) ? a : b;

Templates let you parameterize not data, but data types. What's happening here is that we're defining a little "function factory" which generates code at compile time: It takes one type parameter, T, and it generates a function which expects two (in fact, you can use regular ordinary types for template parameters also, but it's not enough to be generally useful for currying functions or anything like that). Whenever the compiler sees min() in use, it uses this template to generate code for min() with the type parameter -- T in our example -- replaced by the types of arguments passed to the function. The template is a "pattern" used to generate C++ source code. Source code is just text. If you throw in a call to a.foo(), any class with an appropriate member function named foo() will be acceptable to the template. Inheritance is totally irrelevant because we're not fitting different "plugs" into the same "socket". Instead, we're generating new "sockets" as needed.

Here it is in action:

    std::string foo = "foo", bar = "bar";

    //  std::string has an operator<() member function, 
    //  so why not?
    std::string low = min( foo, bar );

    //  Useless, schmuseless!
    int n = min( argc, fileno( stdin ) );

All's well, until ambiguity rears its ugly head. You could easily call min( 6, 3.65 ). Should the compiler assume that T is double1, or int? It can't make that call, so it throws up its hands and says "template parameter 'T' is ambiguous" or some such thing. You can work around that by explicitly providing T:

    n = min<double>( 6, 3.65 );

That's an annoyance. There's a better way:

    template <class T1, class T2>
    inline T1 min( T1 a, T2 b )
        return ( a < b ) ? a : b;

There. We're no longer requiring that the two types be the same. We never had any good reason to do that in the first place. They are whatever they are. The return type nags at my conscience, but it seems to make sense for it to be the lefternmost of the two arguments. A macro would handle that more tactfully: It would return exactly the value that it returns. With macros, there shall be no coercion in types. What happens if we try wildly incompatible types, like a string class and an int? The compiler will generate code for the function if it possibly can. If it can't, it won't, and it'll scold you. If that string class is on the left and it has an operator<() overload for int, you'll be fine.

Let's move on to a more advanced example: A class template.

    template <class T, int SIZE = 128>
    class stack {
        //  Constructor
        stack()  { _end = _data = new T[ SIZE ]; }

        //  Virtual destructors make subclassing safe.
        virtual ~stack()  { delete[] _data; }

        //  Expose size with an anonymous enum, since that's 
        //  the only way to do const member data in C++
        enum { size = SIZE };

        //  _end points one past the top item
        int count() { return _end - _data; }

        T & pop()   { return *--_end; }

        T & top()   { return *(_end - 1); }

        void push( const T & newdata )  { *_end++ = newdata; }

        T * _data;
        T * _end;       //  _end points one past the top item

This works much the same as the function we saw above. We're using references and const references now instead of just throwing T instances around, but a real implementation of min() would have done the same: The objects in question might be large, or copying them might be unwise for other reasons, so it pays to play it safe. The SIZE parameter has a default parameter: If you don't give it a size, it will use 128. Everything else is perfectly ordinary C++ code. Here's how you'd use it:

    stack<int, 16>      st1;
    stack<std::string>  st2;

    st2.push( "foo" );
    st1.push( 456 );

That's very useful: int and std::string are very, very different kinds of things, but we can use the exact same code to store either one in a stack. Furthermore, we're not doing it with unsafe typecasts or ignoring the type completely, the way a macro would. It's typesafe, which in C++ is a big deal.

Here's the catch: It's typesafe, and in C++, that's a big deal. We're working with a relatively low-level language. Each of those objects on that stack has a size. If you want your stack<std::string> to work with subclasses of std::string, you'll need to store pointers instead of object instances, and life (a.k.a. "memory management") becomes more complicated. Each of those objects also has member functions, probably a vtable, and a layout in memory: You may have something that's the same size as std::string and has members with the same names that do the same things, but it's not the same. You could "instantiate" the stack template for both that class and std::string, and the compiler would merrily generate the right code for each one, but once that code is generated, it is absolutely normal C++ code. When it calls a member function, it's calling the function through a function pointer. When it looks at a data member, it's using pointer arithmetic. In C++, names matter only in source code. Templates operate on names, but at runtime that's all been long forgotten. You could use a typecast and try to ram a hierarchically unrelated std::string "look-alike" (and size-alike) into your std::string stack, and that would seem to work until you tried to pull it back out and do anything with it. At that point, the code generated by the compiler will call wong entries in its vtable, play pointer arithmetic based on wildly wrong assumptions about its layout, and most likely crash.

When it comes to coping with heterogenous collections of objects, templates buy you nothing that you didn't already get with old-fashioned inheritance. You can't leave home without a well-designed class hierarchy, and that's that.

To conclude: C++ templates are an elaborate and very powerful mechanism for pretending, in some cases, that the language isn't bound by a rigid object oriented inheritance-hungry type system. Don't make too much of that "bound"/"rigid" rhetoric: That straitjacket of a type system lets the compiler generate wonderfully efficient code, and that's worth the price of admission for many applications.

1 All floating point literals in C++ are promoted to double, whether they need it or not (p 74, The C++ Programming Language 3rd ed. by Bjarne Stroustrup);