44

I am not new to programming, but I am one that started a few years ago, and I do love templates.

But in the before times, how did people deal with situations where they needed compile-time code generation like templates? I'm guessing horrible, horrible macros (at least that's how I'd do it), but googling the above question only gets me pages and pages of template tutorials.

There are many arguments against using templates, and while it typically boils down to readability, "YAGNI", and complaining about how poorly it is implemented, there is not a lot out there on the alternatives with similar power. When I do need to do some sort of compile-time generics and do want to keep my code DRY, how does/did one avoid using templates?

  • 10
    this probably was done same way as in plain C, see Writing generic code when your target is a C compiler – gnat Nov 12 '14 at 16:11
  • 2
    @Telastyn, IIRC, templates were a novelty of CFront 3 (about 1990). – AProgrammer Nov 12 '14 at 16:19
  • 2
    @Telastyn: around the year 2000, most existing C++ compilers did not provide templates very well (even if they pretended to provide it, most of them were too buggy for producion usage). Template support was mostly for supporting generic containers, but far from the requirements to support something like Alexandrescu's "Modern C++ design" examples. – Doc Brown Nov 12 '14 at 18:32
  • 3
    Are you sure that compile-time code generation was used before the power of templates was realized? I was young then, but I am under the impression that in the old days, only the simplest sorts of compile-time code generation were used. If you really wanted to write a program to write your program, you wrote a program/script whose output was C source code, rather than doing so with template language. – user122173 Nov 13 '14 at 8:42
  • 4
    @Joshua - Questions are closed as duplicate if the existing answers to another question address the primary inquiries behind the present question. "Exact" matches are not required; the point is to quickly match the OP with answers for their question. In other words, yes, it's a duplicate. That said, this question smacks of "OMG! How did the World exist before ...?!" which isn't a terribly constructive question. Doc Brown pointed out in an earlier (and now deleted comment) how that phenomenom can affect commentary. – user53019 Nov 15 '14 at 2:47
52

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() {}
 void Add(TYPE value);
private:
 TYPE *list;
 size_t n;
 size_t a;
}

#ifdef WANTIMP
void Collection_ ## TYPE ::Add(TYPE value)
#endif
| improve this answer | |
  • 10
    +1 - There is a book by Bjarne Stroustrup where he tells the history of C++ (found it years ago at the university library), and this technique was explicitly described as a motivation for the development of templates. – Stefan Majewsky Nov 13 '14 at 20:39
  • 2
    Does this technique have a name? Perhaps "X-Macros"? – David Cary Nov 14 '14 at 16:27
46

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.

| improve this answer | |
  • 1
    That works for generic storage, but what about generic functions? @gnat's macros can handle that, but this horrid little class can't. Won't this also lead to a nightmare of strict aliasing problems while processing the data? – IdeaHat Nov 12 '14 at 16:28
  • 1
    @MadScienceDreams Why couldn't you apply this to function addresses? – Panzercrisis Nov 12 '14 at 16:32
  • 3
    @IdeaHat: Yes, it would. But all of this comes from a time when there was much less emphasis on having the tools save the programmer from his own mistakes. In other words, you had to be careful because the language gave you a lot more rope to shoot yourself in the foot. – Blrfl Nov 12 '14 at 16:54
  • 6
    You could know the data type at the other end of the pointer by storing somewhere... perhaps in a table? Maybe a... vtable? This is the sort of stuff the compiler abstracts away for us. In other words, before compilers handled templates and polymorphism, we had to make our own. – user22815 Nov 12 '14 at 17:29
  • 9
    @IdeaHat: For generic functions look at qsort in the C library. It can sort anything because it takes a function pointer for the comparison function and passes a pair of void*'s. – Zan Lynx Nov 13 '14 at 0:26
18

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.

| improve this answer | |
  • We really need a name for the opposite 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. That seems like exactly the blub paradox to me ("Languages less powerful than Blub are obviously less powerful, because they're missing some feature he's used to.") It'd be the opposite if the person knew his language's limitations and could imagine features that solve them. – Doval Nov 12 '14 at 20:53
  • 4
    Opposite isn't quite the word I was going for, but it's the closest I could come up with. The blub paradox presumes the ability to recognize a less powerful language, but doesn't comment on the difficulty of comprehending programming in one. Somewhat counterintuitively, the ability to program in a more powerful language doesn't confer a commensurate ability to program in a less powerful one. – Karl Bielefeldt Nov 12 '14 at 21:17
  • 2
    I suspect "converse" is the word you're looking for: "A situation, object, or statement that is the reverse of another or corresponds to it but with certain terms transposed" – Jules Nov 13 '14 at 7:28
9

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.

Here's the man page for genclass: http://manpages.ubuntu.com/manpages/dapper/man1/genclass.1.html

| improve this answer | |
7

[To the OP: I'm not trying to pick on you personally, but raise your and others' awareness of thinking about the logic of the question(s) asked on SE and elsewhere. Please don't take this personally!]

The title of the question is good, but you are severely limiting the scope of your answers by including '... situations where they needed compile-time code generation.' Many good answers to the question about how to do compile-time code generation in C++ without templates exist on this page, but to answer the question you originally posed:

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.

Please, think about logical fallacies in your posts before you post.

[Thank you! Please, no harm intended here.]

| improve this answer | |
  • 11
    I think you're being unduly pedantic. The OP did not phrase his question as well as he could have. However I think it's pretty clear that he wanted to ask something like "how did people create generic functions before templates". I think in this case the appropriate action would have been to edit his answer or leave a comment rather than give a rather patronising lecture. – scytale Nov 14 '14 at 12:55
6

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

| improve this answer | |
5

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.

| improve this answer | |
1

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();
| improve this answer | |
1

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"

| improve this answer | |

Not the answer you're looking for? Browse other questions tagged or ask your own question.