Click here to Skip to main content
15,867,453 members
Articles / Programming Languages / C++

Compile Time Map

Rate me:
Please Sign up or sign in to vote.
4.93/5 (8 votes)
29 May 2013CPOL5 min read 20.7K   16   3
A map storing key-value/s and allowing data retrieval and other operations all at compile time

Introduction

This is an attempt to present compile time utilities that lead to formation of a "map" data structure (no ordering) on which operations can be done at compile time. This could have advantage of catching illegal operations at compile time and zero runtime overhead in general.

Background

Audience is expected to be a little familiar with Policy Based Design and specially template recursions used in template meta-programming. 

Using the code 

{The construction of scenario here is highly tailored to explain how and a bit of why to create the compile time construct under discussion. Once done the actual use cases might be evident in the practical world}

To demonstrate, let's consider an arbitrary use case: 

Below, user defined data type <code>Derived (which is a struct) is a host class which can have any of the policies (policy classes PolicyZero, PolicyOne etc) as it's base class. We want to store it in a container against an enum. So we also have a non-templated class Base, which also Derived derives from. The functionality of each of the classes here is not important; just assume they are needed. So now we can have a map of enum against polymorphic type Base* to store different constructions of class template Derived

We have the following:  

C++
enum eLabel
{
    eTagOne,
    eTagTwo,
    eTagThree
};

struct Base
{
    Base(eLabel label) m_label(label) {}
    eLabel m_label;
};

template<typename DataType, typename Host>
struct PolicyZero
{
};

template<typename DataType, typename Host>
struct PolicyOne
{
};

template<typename DataType, template<typename, typename> class Policy>
struct Derived : Base, Policy<DataType, Derived<DataType, Policy>>
{
    Derived(eLabel label) : Base(label) {}
};

using BaseMap = std::map<eLabel, Base*>;
BaseMap baseMap;

//construction of Derived:
baseMap.insert(BaseMap::value_type(
      eTagOne, new Derived<int, PolicyZero> {eTagOne}));
baseMap.insert(BaseMap::value_type(eTagTwo, 
      new Derived<std::string, PolicyOne> {eTagTwo}));
baseMap.insert(BaseMap::value_type(eTagThree, 
      new Derived<double, PolicyZero> {eTagThree}));


template<template<typename, typename> class Policy, typename DataType>
void set(eLabel label, const DataType &refData)
{
    auto it = baseMap.find(label);
    if(it != baseMap.end())
    {
        Derived<DataType, Policy> *pDerived = 
             dynamic_cast<Derived<DataType, Policy>*>(*it);
        if(pDerived)
        {
            //use pDerived
        }
    }
}

Problem: when set(..) is called too many times dynamic_cast led to severe reduction in execution speed. Modifying to static_cast is not safe. For instance consider:

C++
std::string param {"hello"};
set<PolicyOne>(eTagOne, param);
//undefined behaviour with static_cast because here the
//DataType is deduced as std::string whereas it should have been int.

Observation: The exact dynamic type of Base* in BaseMap is known at compile time which depends on eLabel. eLabel is enum, a compile time construct. Hence the dynamic type of Base* in set(..) should be retrievable at compile time ensuring static_cast  is safe.

Solution: Try and create a mapping of (eLabel) with (type and policy). 

Properties:

<1> Traversal and retrieval should be possible at compile time.

<2> There should be no upper bound to the size of the map except because of compiler limitation.

We will define only forward iteration for the map (for simplicity).

We will define operation to find the values (type and policy) stored against a key (eLabel).

C++
//declare policies the map will use
template<typename, typename> class PolicyZero;
template<typename, typename> class PolicyOne;

/*!
 * \brief Compile Time Map.
 * \details Only declared, never defined, to prevent reserving any run-time memory space
 */
template<eLabel MapKey, typename DataType, 
      template<typename, typename> class Policy, typename NextNode>
struct CompileTimeMap;

/*!
 * \brief Signifies the end of map.
 * \details When supplied key is not found in the map, the compiler will 
 * emit errors at compile time mentioning the name of this struct which
 * would make it immediately apparent what went wrong. Only declared, never defined
 */
struct ERROR_Cannot_Find_Passed_eDataLabel_in_Map;
C++
using MapTerminator = ERROR_Cannot_Find_Passed_eDataLabel_in_Map;

Now we should be able to chain as many CompileTimeMap's as we want. The language feature that allows this is Variadic Templates. However in variadic templates we can have only one (type or non-type) arg-pack which should appear as the last template parameter. We must bunch the key-values (key: eLabel AND values: type & policy) into a single type so that we can give it to a variadic template which takes variable number of types as arg-pack. This will be clear after we see it being done. Let's call it Triplet as it bunches 3 things into a type. So we have: 

C++
/*! 
 * \brief Pack all type and non-type arguments of templates
 * into a single type which is this struct itself.
 * \details Only declared, never defined
 */
template<eLabel KeyToPack, typename DataTypeToPack, 
          template<typename, typename> class PolicyToPack>
struct Triplet;

/*!
 * \brief Base Template For Chaining Key-Values into a chained map.
 * \details Base case is not defined. Only declared.
 * This ensures that no one can use it for any other types except for ones for which
 * specializations are defined.
 */
template<typename...> struct GetMap;

/*!
 * \brief Specialized for template Triplet.
 * \details This is the base case for the specialization.
 * It will compile-time-recurse to various copies of itself until arg-pack has no more
 * arguments. We extract the details from template Triplet to feed it to CompileTimeMap.
 */
template<eLabel KeyToPack, typename DataTypeToPack, 
  template<typename, typename> class PolicyToPack, typename... Types>
struct GetMap<Triplet<KeyToPack, DataTypeToPack, PolicyToPack>, Types...>
{
   using MAP = CompileTimeMap<KeyToPack, DataTypeToPack, 
                   PolicyToPack, typename GetMap<Types...>::MAP>;
};

/*!
 * \brief Specialized for template Triplet.
 * \details This is the terminal case for compile-time-recursion
 * and will occur when arg-pack contains only one Triplet.
 * We extract the details from template Triplet to feed it to CompileTimeMap.
 */
template<eLabel KeyToPack, typename DataTypeToPack, 
     template<typename, typename> class PolicyToPack>
struct GetMap<Triplet<KeyToPack, DataTypeToPack, PolicyToPack>>
{
   using MAP = CompileTimeMap<KeyToPack, DataTypeToPack, PolicyToPack, MapTerminator>;
};

That's it! 

Now just populate the map (or add to it if already created and more entries are required during future developments): 

C++
using MAP =
GetMap<
   Triplet<eTagOne, int, PolicyZero>,
   Triplet<eTagTwo, std::string, PolicyOne>,
   Triplet<eTagThree, double, HasMinMaxPolicy>,
>::MAP;

To prevent user from making a mistake while creating Derived, we will change the template definition to following:

C++
template<eLabel label>
struct Derived : Base, {{we should be able to extract what goes here from our map}}
{....}; 

To be able to extract values we need a find operation defined, which if given a compile time map and a key would make it possible to retrieve various values it stores against that key. Key for us is eLabel and values are type & policy. 

C++
/*! 
 * \brief Base Template For Finding Values against a Key in a compile-time-chained map.
 * \details Base case is not defined. Only declared. This ensures
 * that no one can use it for any other types except for ones for which
 * specializations are defined.
 */
template<typename, eLabel> struct Find;


/*!
 * \brief Specialized for Finding Values in template CompileTimeMap.
 * \details This is the base case for the specialization. 
 * It will compile-time-recurse to various copies of itself until KeyToFind matches
 * MapKey in CompileTimeMap.
 */
template<eLabel MapKey, typename DataType, template<typename, 
        typename> class Policy, typename NextNode, eLabel KeyToFind>
struct Find<CompileTimeMap<MapKey, DataType, Policy, NextNode>, KeyToFind>
{
   using ResultDataType = typename Find<NextNode, KeyToFind>::ResultDataType;
   template<typename T, typename U>
   using ResultPolicy = typename Find<NextNode, KeyToFind>::template ResultPolicy<T, U>;
};

/*!
 * \brief Specialized for Finding Values in template CompileTimeMap.
 * \details This is the terminal case for compile-time-recursion
 * and will occur when KeyToFind matches corresponding Key in CompileTimeMap.
 */
template<eLabel KeyToFind, typename DataType, 
   template<typename, typename> class Policy, typename NextNode>
struct Find<CompileTimeMap<KeyToFind, DataType, Policy, NextNode>, KeyToFind>
{
   using ResultDataType = DataType;
   template<typename T, typename U>
   using ResultPolicy = Policy<T, U>;
};

So there we go. So to find Data type against a key we will use the construct:

C++
typename Find<MAP, eTagOne>::ResultDataType;

and to find the policy class we will use:

C++
Find<MAP, eTagOne>::template ResultPolicy;

Now we will rewrite our Derived's definition and set(..) function.

C++
#define Label someLabel
#define PolicyClass Find<MAP, Label>::template ResultPolicy<typename 
   Find<MAP, Label>::ResultDataType, Derived<Label>>

template<eLabel Label>
struct Derived : Base, PolicyClass
{
    Derived() : Base {Label} {}
}; 

and for set(..)

C++
template<eLabel Label, typename DataType>
void set(const DataType &refData)
{
    auto it = baseMap.find(label);
    if(it != baseMap.end())
    {
        Derived<Label> *pDerived {static_cast<Derived<Label>*>(*it)};//note: static_cast
        //use pDerived
    }
}

 Summary 

The point here is try to identify what can be done at compile time and what cannot. Once we do this we might get a lot of cases where the decisions need not be postponed until run-time. For instance, here we could have easily used std::map of eLabel against string representations of data type and policy which Derived is composed of. We would search this map each time set(..) was called and branch to do static_cast according to the retrieved strings. We can immediately see the downsides. <1> mistakes in stringification of policies and data types will lead to wrong branching and thus undefined static_cast's. <2> Need to touch set(..) on every addition of new data type or policy class. <3> When we have huge number of enums (here for the sake of example we had only three) dynamic_cast's will outperform std::map traversal (a run-time penalty). The list goes on.

After carefully weighing the advantages and disadvantages (code bloat in case of using templates maybe) of different approaches, we should implement the one that seems just correct. However the difficult part is that we must 'know' the different approaches. The selection criteria could be affected by newer developments in the language front itself. For example, the way things are done here could be so not straight forward had C++ not introduced variadic templates which has made some great idioms possible. There would have been an upper bound to the map's size determined by some ugly (which previously could be called clever) preprocessor meta-programming.

Personally I believe that such constructs are more interesting when specially the Key is a non-type template parameter. References can be one of them and we can have a reference to almost anything that one would want to fit in as a Key. You can try and make your own compile-time-evaluated maps on these lines with all the benefits of compile time guarantees, zero run-time look up cost (in the above construct, the map traversal and find complexity is O(1) irrespective of the size of the map) etc. 

License

This article, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)


Written By
United States United States
This member has not yet provided a Biography. Assume it's interesting and varied, and probably something to do with programming.

Comments and Discussions

 
GeneralMy vote of 5 Pin
Ștefan-Mihai MOGA13-Jun-13 20:44
professionalȘtefan-Mihai MOGA13-Jun-13 20:44 
GeneralRe: My vote of 5 Pin
Spandan_Sharma27-Jun-13 3:32
Spandan_Sharma27-Jun-13 3:32 
GeneralMy vote of 5 Pin
Member 869379426-May-13 22:46
Member 869379426-May-13 22:46 

General General    News News    Suggestion Suggestion    Question Question    Bug Bug    Answer Answer    Joke Joke    Praise Praise    Rant Rant    Admin Admin   

Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads, Ctrl+Shift+Left/Right to switch pages.