255mph intro to C++ Templates

2015-06-20 21:37 by Ian

This is an entry from the Manuvr Blog that I am cross-posting here.

When writing programs (no matter the language [human or otherwise]), you will repeat yourself. Unavoidable.

Templates are a C++ feature that allow us to write the form of the code once, and rely on the compiler to replicate it for each unique type we use with it. The Java-enabled among you will recognize this idea as generics, and will probably want to graze this post for style differences or skip it entirely.

TL;DR (what is this notation?)

In a template, when you see...

LinkedList<T>

...just know that "T" is "any type you want".

Why do templates exist?

Consider....

class SomeDataType {
  public:
    SomeDataType();   // Constructor
    ~SomeDataType();  // Destructor

    bool reticulate_splines();
    bool goto_space_today();
};

class SomeOtherDataType {
  public:
    SomeOtherDataType();   // Constructor
    ~SomeOtherDataType();  // Destructor

    void make_cookies(int cookie_count);
};


void some_fxn(SomeDataType* argument) {
  if (argument->reticulate_splines()) {
    goto_space_today();
  }
  return;
}

SomeDataType       instance_0;
SomeOtherDataType  instance_1;

Because we are strongly-typed, we are unable to...

some_fxn(&instance_1);

...unless we start juggling knives...

some_fxn((SomeDataType*) &instance_1);

...and that might work as you want in the case of a direct inheritance relationship (IE, if SomeOtherDataType extends SomeDataType). But if SomeDataType and SomeOtherDataType are radically different objects, you will generate some hilarious bugs.

Now... if the compiler doesn't give the simple cast a 'pass', and we want to try juggling chain-saws, we can type-pun...

some_fxn((SomeDataType*) (void*) &instance_1);

...and compiler might be coaxed into building it. But it is sure to give bad results or (hopefully) outright crash if you run it. It will do this because the compiler, like any good tool, will do what you say and not what you meant. And if you've ever had another engineer hand you three live chain-saws at once, you understand how easy it is to make a mistake.

So where does that leave us?

Without C++, those are basically our only two options if we don't want to re-write (and maintain) the same code for each type; cast, or type-pun. In the best-case, we are still juggling knives.

A template's anatomy

Templates amount to nothing more than instructions to the compiler to repeat the declaration of code, rather than forcing you to do it explicitly. But this does not save us the responsibility of definition. So we define the thing that we want replicated, and we do it once...

// Definition (belongs in a header file)
template <class T> class TemplatedClass {
  public:
    TemplatedClass(T arg) {   // Constructor
      member = arg;
    };

    ~TemplatedClass() {};

    void doStuffToMember() {
      /* I like to inline my templates completely,
         and so I would have actual code here in my 
         header, but you could also write the code
         into a separate Cpp file. */
    };

  private:
    T member;
};


// Instantiation (belongs in a Cpp file)
TemplatedClass<SomeDataType*> concrete_0(&instance_0);

// Usage
concrete_0.doStuffToMember();

TemplatedClass in this case is written as a class. It therefore refers to a body of code (a vtable), as well as a type, and a set of data members. But a template might also be used with struct (only data members) or a function (only vtable).

I can then effortlessly add...

TemplatedClass<SomeOtherDataType*> concrete_1(&instance_1);

...and not have to worry about casting ever again, because I have abstracted the notion of doStuffToMember() away from the nature of particular kinds of members I might do stuff to.

What we bought with this linguistic shell game

The reliability benefit consists of a very strong linguistic check on the sort of mistake highlighted above. If I try to...

TemplatedClass<SomeOtherDataType*> concrete_fail(&instance_1);

...the compiler will once again demand that I cast my argument. But this time I know that I have no reason to do so because the template should have made two copies of the code for TemplatedClass (one for each type), and therefore it can only be the case that I am trying to use the wrong one.

We also got a maintenance benefit, because now we only need to maintain the Template, and all copies of that template made at compile time contain whatever features &/| fixes we've made. The maintenance benefit therefore cascades into a secondary reliability benefit, because we don't have to worry that a fix wasn't applied over there and botched, but not botched in this other place.

We also don't have the CPU burden of inheritance (additional indexed-jump instructions due to vtables). This is a bare-metal benefit, that we might cover later.

What the game cost us

Code size. Whatever the compiled size of TemplatedClass is, it will be doubled if we use that template with two types. Three types? It will triple. This is a trivial concern with the tinker-toy program presented here, but if your template's compiled size is 1KB, and you only have 8KB to store your program, then you can only use your template with 8 distinct types before you run out of code space. If that is your situation, the costs of using a template are too high for your application.

From a run-time perspective, we have traded program size for execution speed.

Full source code used to develop this post

Below is pasted the compilable (brevity-free) program I used to test my assertions in this post. It can be compiled with...

g++ -o test test.cpp


    #include 
    #include 


    class SomeDataType {
      public:
        int x;

        SomeDataType() {  x = 1; };   // Constructor
        
        ~SomeDataType() {};           // Destructor

        bool reticulate_splines() {  
          printf("Splines reticulated. x = %d\n", x);
          return true; 
        };

        bool goto_space_today() {
          printf("We went to space.\n");
          return true;   
        };
    };

    class SomeOtherDataType {
      public:
        float y;
        int x;

        SomeOtherDataType() {   // Constructor
          x = 9; 
          y = 5.1f;
        };

        ~SomeOtherDataType() {};             // Destructor

        void make_cookies(int cookie_count) {
          printf("I've made %d cookies.\n", cookie_count);
        };
    };


    // Definition (belongs in a header file)
    template  class TemplatedClass {
      public:
        TemplatedClass(T arg) {   // Constructor
          member = arg;
        };

        ~TemplatedClass() {};

        void doStuffToMember() {
          /* I like to inline my templates completely,
             and so I would have actual code here in my 
             header, but you could also write the code
             into a separate Cpp file. */
          printf("Doing stuff to the member.\n");
        };
  
      private:
        T member;
    };


    void some_fxn(SomeDataType* argument) {
      if (argument->reticulate_splines()) {
        argument->goto_space_today();
      }
      return;
    }




    int main() {
        SomeDataType       instance_0;
        SomeOtherDataType  instance_1;

        // Instantiation (belongs in a Cpp file)
        TemplatedClass concrete_0(&instance_0);
        TemplatedClass concrete_1(&instance_1);

        // Uncomment to see gcc fail because we mis-used our template.
        //TemplatedClass concrete_fail(&instance_0);

        // This shows the correct behavior. x is ALWAYS == 1.
        some_fxn(&instance_0);
  
        // This angers gcc...
        //some_fxn(&instance_1);
  
        /* 
         * gcc let's these slide, but it will give us bad results,
         * and it would take an expert to know why. 
         * Very subtle bugs...
         */
        // Uncomment the line below to juggle knives.
        some_fxn((SomeDataType*) &instance_1);
        // Uncomment the line below to juggle live chain-saws.
        some_fxn((SomeDataType*) (void*) &instance_1);
    
        // Uncomment the line below to see the binary size increase.
        // Where did all that extra bloat come from? :-)
        //TemplatedClass concrete_0(&instance_1);

        // Usage of template.
        concrete_0.doStuffToMember();
        concrete_1.doStuffToMember();

        return 0;
    }

Previous:
Next: