https://github.com/ayushbansal07/Cpp-miniprojects/tree/main/001_compiletimelist

Introduction

Imagine you have a usecase where you’d like to do some operation on list of some objects that follow a similar interface. For example, you have a list of checks in your code, and want to verify that your input passes all those checks?

An easy way to do that is through the use of inheritance. Something like this -

#include <iostream>
#include <vector>

class BaseCheck {
public:
  virtual bool check() = 0;
};

class Check1 : public BaseCheck {
public:
  virtual bool check() override {
    return true;
  }
};

class Check2 : public BaseCheck {
public:
  virtual bool check() override {
    return false;
  }
};

int main() {
  std::vector<BaseCheck*> checks;
  Check1 check1;
  Check2 check2;
  checks.push_back(&check1);
  checks.push_back(&check2);

  bool result = false;
  for (auto c : checks) {
    result &= c->check();
  }
  std::cerr << result << std::endl;
  return 0;
}

But virtual functions are slow. And especially for fast path applications, they are not the preferred option. So, is there a way for us to achieve similar functionality, but in a more efficient manner?

Using Templates

Templates are an amazing tool to move run-time behaviour to compile-time. Through Variadic templates, we can define a list, which takes the type of objects as template parameters and calls our desired function on each instance of the object.

Here is an implementation of a CompileTimeList for the usecase defined above (check simplelist). Let us explore it in detail.

The Code

Let us focus on the simplelist first. The SimpleList Class interface looks something like this -

// include/simplelist/simplelist.h

template <typename... TObjs>
class SimpleList {
public:
  void init() {
    m_node.init();
  }

  bool check() {
    return m_node.check();
  }

protected:
  typename SimpleNodeTypeSelector<TObjs...>::type m_node;
};

It takes the objects’ types as template arguments and expose two functions on them - init() and check().

We will revisit the last line of the code in the end.

List Nodes

We define the interface of the list nodes inside simplelistnode.h.

// include/simplelist/simplelistnode.h

template <typename TObj, typename TNextNode>
class SimpleListNode {
public:
  void init() {
    m_obj.init();
    m_next.init();
  }

  bool check() {
    return m_obj.check() && m_next.check();
  }

protected:
  TObj m_obj;
  TNextNode m_next;
};

Each node takes 2 template arguments - the type of the object it holds, and the type of the next node. It contains 2 protected members - m_node and m_next.

Inside init(), we call the init() function of the object and then recursively call init() of next node. Similarly for check().

We also define a SimpleListNodeTerminal class that does not contain a next node and ends the recursion.

// include/simplelist/simplelistnode.h

template <typename TObj>
class SimpleListNodeTerminal {
public:
  void init() {
    m_obj.init();
  }

  bool check() {
    return m_obj.check();
  }

protected:
  TObj m_obj;
};

Understanding the type of each Node

So now, let us understand the type of each Node. Let’s say we want our list to contain 3 objects - Check1, Check2, Check3.

The type of the last node will be SimpleListNodeTerminal<Check3> (because its the last node and we should not call check any further). m_node will be of type Check3.

The type of the second node will be
SimpleListNode<Check2, SimpleListNodeTerminal<Check3>>. So m_node inside this will be of type Check2 and m_next of type SimpleListNodeTerminal<Check3>.

The type of the first node will be
SimpleListNode<Check1, SimpleListNode<Check2, SimpleListNodeTerminal<Check3>>>.

The first node resides inside the SimpleList class as m_node object. So on calling init() for SimpleList, it calls init() for m_node which is the first node, which will call init() for the Check1 object. Then, it calls init() for next node which calls init() for Check2 object followed by the init() call for Terminal object which only calls init() for Check3 and our init() call of the list is now complete.

How to find the type of First Node

The most complicated part is how do we determine the type of first node? For this we have used something called template meta-programming. We declare a type selector class, which given a list of objects, defines the type of the Node class (inside ::type member type).

// include/simplelist/simplenodetypeselector.h

template <typename... TObjs>
struct SimpleNodeTypeSelector;

// include/simpletlist/simplenodetypeselector.hpp

template <typename TObj>
struct SimpleNodeTypeSelector<TObj> {
  using type = SimpleListNodeTerminal<TObj>;
};

template <typename TObj, typename... TObjList>
struct SimpleNodeTypeSelector<TObj, TObjList...> {
  using type = SimpleListNode<TObj, typename SimpleNodeTypeSelector<TObjList...>::type>;
};

We then provide 2 definitions of it -

A type selector class when only 1 object is present (base condition). In this case, the type of the node is the Terminal Object (as we saw in our example).

A type selector class when more than 1 object is present - In this case the type is a SimpleListNode with first template argument being the first Object in that list and then we recursively find the type of the next node using our type selector class.

If you are new to template meta-programming, the above code translates to something like this -

// Pseudo code

def findType(objList):
  if len(objList) == 1: # first definition
    return SimpleListNodeTerminal(objList[0])
  else: # 2nd definition
    return SimpleListNode(objList[0], findType(objList[1:] ))

The good thing about this is, this entire type deduction happens at compile-time.

Coming back to the main list, the type of the first node can be derived using the selector class by passing all the object types to it.

The main()

src/simplelisttest.cpp tests our SimpleList with 4 TestObjects (defined inside inlcude/simplelist/objimpl.h) implementing an init() and check() function.

// src/simplelisttest.cpp

int main() {
  SimpleList<TestObj1, TestObj2, TestObj3, TestObj4> list;
  list.init();
  std::cerr << list.check() << std::endl;
  return 0;
}

Booleanlist

The booleanlist/ folder defines an extension of our simple list. It is very similar to simplelist, but it expects an additional operator enum (OR / AND) which defines whether the check() operation is AND type or OR.

The purpose of booleanlist is just to demonstrate that this basic template of a compile time list can be extended as per your use cases. I skip over the details of booleanlist in this blog post.