Besides the void * pointer which is covered in Robert’s answer, a technique like this was used (Disclaimer: 20 year old memory):

#define WANTIMP

#define TYPE int
#include "collection.h"
#undef TYPE

#define TYPE string
#include "collection.h"
#undef TYPE

int main() {
    Collection_int lstInt;
    Collection_string lstString;
}

Where I have forgotten the exact preprocessor magic inside collection.h, but it was something like this:

class Collection_ ## TYPE {
public:
 Collection_ ## TYPE () {}
 void Add(TYPE value);
private:
 TYPE *list;
 size_t n;
 size_t a;
}

#ifdef WANTIMP
void Collection_ ## TYPE ::Add(TYPE value)
#endif

The traditional way to implement generics without having generics (the reason templates were created) is to use a void pointer.

typedef struct Item{ 
        void* data;
    } Item;

typedef struct Node{
    Item Item; 
    struct Node* next; 
    struct Node* previous;
} Node;

In this example code, a binary tree or doubly-linked list can be represented. Because item encapsulates a void pointer, any data type can be stored there. Of course, you would have to know the data type at runtime so that you can cast it back to a usable object.

As other answers pointed out, you can use void* for generic data structures. For other kinds of parametric polymorphism, preprocessor macros were used if something got repeated a lot (like dozens of times). To be honest, though, most of the time for moderate repetition, people just copied and pasted, then changed the types, because there are a lot of pitfalls with macros that make them problematic.

We really need a name for the converse of the blub paradox, where people have a hard time imagining programming in a less expressive language, because this comes up a lot on this site. If you’ve never used a language with expressive ways of implementing parametric polymorphism, you don’t really know what you’re missing. You just sort of accept the copying and pasting as somewhat annoying, but necessary.

There are inefficiencies in your current languages of choice that you aren’t even aware of yet. In twenty years people will be wondering how you eliminated them. The short answer is you didn’t, because you didn’t know you could.

I remember when gcc shipped with genclass – a program which took as input a set of parameter types (e.g. key and value for a Map) and a special syntax file which described a parameterized type (say, a Map or a Vector) and generated a valid C++ implementations with the param types filled in.

So if you needed Map<int, string> and Map<string, string> (this was not the actual syntax, mind that) you had to run that program twice to generate something like map_string_string.h and map_int_string.h and then use these in your code.

See the man page for genclass and the documentation from GNU C++ Library 2.0 for more detail.

What did people do before templates in C++?

The answer is, of course, they (we) didn’t use them. Yes, I am being tongue-in-cheek, but the details of the question in the body seem to (perhaps exaggeratedly) assume that everyone loves templates and that no coding could ever have been done without them.

As an example, I completed many many coding projects in various languages without needing compile-time code generation, and believe others have also. Sure, the problem solved by templates was an itch large enough that someone actually scratched it, but the scenario posited by this question was, largely, non-existent.

Consider a similar question in cars:

How did drivers shift from one gear to another, using an automated method which shifted gears for you, before the automatic transmission was invented?

The question is, of course, silly. Asking how a person did X before X was invented isn’t really a valid question. The answer is generally, ‘we didn’t do it and didn’t miss it because we didn’t know it ever would exist’. Yes, it’s easy to see the benefit after-the-fact, but to assume that everyone was standing around, kicking their heels, waiting for automatic transmission, or for C++ templates, is really not true.

To the question, ‘how did drivers shift gears before the automatic transmission was invented?’ one can reasonably answer, ‘manually,’ and that’s the type of answers you are getting here. It may even be the type of question that you meant to ask.

But it wasn’t the one you did ask.

So:

Q: How did people use templates before templates were invented?

A: We didn’t.

Q: How did people use templates before templates were invented, when they needed to use templates?

A: We didn’t need to use them. Why assume we did? (Why assume we do?)

Q: What are alternative ways to achieve the results that templates provide?

A: Many good answers exist above.

Horrible macros is right, from http://www.artima.com/intv/modern2.html:

Bjarne Stroustrup: Yes. When you say, “template type T,” that is really the old mathematical, “for all T.” That’s the way it’s considered. My very first paper on “C with Classes” (that evolved into C++) from 1981 mentioned parameterized types. There, I got the problem right, but I got the solution totally wrong. I explained how you can parameterize types with macros, and boy that was lousy code.

You can see how an old macro version of a template was used here: http://www.xvt.com/sites/default/files/docs/Pwr++_Reference/rw/docs/html/toolsref/rwgvector.html

As Robert Harvey already said, a void pointer is the generic data type.

An example from the standard C library, how to sort an array of double with a generic sort:

double *array = ...;
int size = ...;   
qsort (array, size, sizeof (double), compare_doubles);

Where compare_double is defined as:

int compare_doubles (const void *a, const void *b)
{
    const double *da = (const double *) a;
    const double *db = (const double *) b;
    return (*da > *db) - (*da < *db);
}

The signature of qsort is defined in stdlib.h:

void qsort(void *base, size_t nmemb, size_t size,
    int (*compar)(const void *, const void *)
);

Note that there is no type checking at compile time, not even at run time. If you sort a list of strings with the comparator above that expects doubles, it will happily try to interpret the binary representation of a string as a double and sort accordingly.

One way of doing this is like this:

https://github.com/rgeminas/gp–/blob/master/src/scope/darray.h

#define DARRAY_DEFINE(name, type) DARRAY_TYPEDECL(name, type) DARRAY_IMPL(name, type)

// This is one single long line
#define DARRAY_TYPEDECL(name, type) 
typedef struct darray_##name 
{ 
    type* base; 
    size_t allocated_mem; 
    size_t length; 
} darray_##name; 

// This is also a single line
#define DARRAY_IMPL(name, type) 
static darray_##name* darray_init_##name() 
{ 
    darray_##name* arr = (darray_##name*) malloc(sizeof(darray_##name)); 
    arr->base = (type*) malloc(sizeof(type)); 
    arr->length = 0; 
    arr->allocated_mem = 1; 
    return arr; 
}

The DARRAY_TYPEDECL macro effectively creates a struct definition (in a single line), replacing name with the name you pass, and storing an array of the type you pass (the name is there so that you can concatenate it to the base struct name and still have a valid identifier – darray_int * is not a valid name for a struct), while the DARRAY_IMPL macro defines the functions that operate on that struct (in that case they’re marked static just so that one would only call the definition once and not separate everything).

This would be used as:

#include "darray.h"
// No types have been defined yet
DARRAY_DEFINE(int_ptr, int*)

// by this point, the type has been declared and its functions defined
darray_int_ptr* darray = darray_int_ptr_init();

I think templates get used a lot as a way to reuse container types that have a lot of algorithmic values such as dynamic-arrays (vectors), maps, trees, etc. sorting, etc.

Without templates, necessarily, these contain implementations are written in a generic way and are given just enough information about the type required for their domain. For instance, with a vector, they just need the data to be blt’able and they need to know the size of each item.

Let’s say you have a container class called Vector that does this. It takes void*. The simplistic usage of this would be for the application layer code to do a lot of casting. So if they are managing Cat objects, they have to cast Cat* to void*, and back all over the place. Littering application code with casts has obvious problems.

Templates solve this.

Another way to solve it is to create a custom container type for the type you’re storing in the container. So if you have a Cat class, you’d create a CatList class derived from Vector. You then overload the few methods that you use, introducing versions that take Cat objects instead of void*. So you’d overload the Vector::Add(void*) method with Cat::Add(Cat*), which internally simply passes the parameter to Vector::Add(). Then in your application code, you’d call the overloaded version of Add when passing in a Cat object and thus avoid casting. To be fair, the Add method wouldn’t require a cast because a Cat* object converts to void* without a cast. But the method to retrieve an item, such as the index overload or a Get() method would.

The other approach, the only example of which I recall from the early 90s with a large application framework, is to use a custom utility that creates these types over classes. I believe MFC did this. They had different classes for containers like CStringArray, CRectArray, CDoulbeArray, CIntArray, etc. Rather than maintain duplicate code, they did some type of meta-programming similar to macros, using an external tool that would generate the classes. They made the tool available with Visual C++ in case anyone wanted to use it — I never did. Maybe I should have. But at the time, the experts were touting, “Sane subset of C++” and “You don’t need Templates”