Search code examples
c++templatesmetaprogrammingkey-valuetemplate-meta-programming

Creating compile-time Key-Value map in C++

I have tried to create a compile-time simple Key-Value map in C++. I'm compiling with /std:c++11. (Using IAR compiler for embedded code and only cpp++11 is supported at the moment)

I've learnt a little bit about meta-programming.

I don't want my map to have a default value, if key is not found, like this post: How to build a compile-time key/value store?

I want to get compiler error, if in my code I'm trying to get a value which is not stored in the map.

Here is what I've done:


#include <iostream>




template <int kk, int vv>
struct KeyValue
{
    static const int k = kk, v = vv;
};


// Declaration 
template <typename kv, typename...>
struct CompileTimeMap;


// Recursive Definition 
template<typename kv, typename... rest>
struct CompileTimeMap<kv, rest...>
{
    template<int k_input>
    struct get
    {
        static const int val = (k_input == kv::k) ? kv::v : CompileTimeMap<rest...>::get<k_input>::val;
    };
};


// Base Definition 
template <typename kv>
struct CompileTimeMap<kv>
{
    template<int k_input>
    struct get
    {
        static const int val = (k_input == kv::k) ? kv::v;
    };
};




// ----------------------------- Main  -----------------------------

typedef CompileTimeMap<KeyValue<10, 20>, KeyValue<11, 21>, KeyValue<23, 7>> mymap;

int main()
{
    // This calles should be ok !! :) 
    std::cout << mymap::get<10>::val << std::endl;
    std::cout << mymap::get<11>::val << std::endl;
    std::cout << mymap::get<23>::val << std::endl;


    // This line should resolve a compile error !! (there is no key of 33) 
    std::cout << mymap::get<33>::val << std::endl;
}

I get the following error: error C2131: expression did not evaluate to a constant.

How can I make this work? Many thanks :)

Solution

  • Don't write a template metaprogram, where it is not necessary. Try this simple solution (CTMap stands for compile time map):

    template <class Key, class Value, int N>
class CTMap {
public:
    struct KV {
        Key   key;
        Value value;
    };

    constexpr Value  operator[](Key key) const
    {
        return Get(key);
    }

private:
    constexpr Value  Get(Key key, int i = 0) const
    {
        return i == N ?
               KeyNotFound() :
               pairs[i].key == key ? pairs[i].value : Get(key, i + 1);
    }

    static Value KeyNotFound()      // not constexpr
    {
        return {};
    }

public:
    KV  pairs[N];
};


constexpr CTMap<int, int, 3>  ctMap{{ { 10, 20 }, { 11, 21 }, { 23, 7 } }};


static_assert(ctMap[10] == 20, "Error.");
static_assert(ctMap[11] == 21, "Error.");
static_assert(ctMap[23] ==  7, "Error.");

// constexpr auto compilationError = ctMap[404];

    You will get a compilation error, if you uncomment the last line (live demo). The compiler will direct you to the KeyNotFound() : line, from which the reason of the failure should be obvious.

    Remarks

    • The member variable pairs is made public, to make it possible to initialize the map using aggregate initialization.
    • The given N and the number of pairs that initialize CTMap should match. If N is less, you get a compilation error. If N is greater, zero-initialized pairs ({ 0, 0 }) will be silently added to pairs. Pay attention to this.
    • The (compiler generated) constructor does not check for duplicate keys. operator[] will find the first, but the intended usage is that you do not initialize CTMap with duplicate keys.
    • Recursion is not necessary in C++14. We can write a for loop in a constexpr function (live demo). The linked implementation gives another idea for giving a compiler error in case the key is not found: an exception is thrown. The member variable pairs is made private.

    Intended to be used in compile time

    This is a linear map, and parameters are passed by value. My intention was that the map will be used in compile time evaluated code, where this should not be a problem.

    Note also that when evaluated in run time, this class won't give any feedback if the key is not found in the map.

    Let's take a closer look of how ctMap[10] works in different situations. I have tried the following with three compilers (MSVC v19.24, clang 10.0.0, gcc 9.3).

    • constexpr int C = ctMap[10]; – The global constant C will be initialized with 20 even in debug builds. No computation is made during run-time. Note that to ensure, that the global will be created, you have to take its address somewhere. If you use the value of C, its value (20) will be substituted where it is used, and C won't be created in the object file even in debug builds.
    • int Foo() { return ctMap[10]; } – In debug builds operator[] will be called. In release builds MSVC inlines operator[] to Foo, i.e. eliminates one call, but the resulting code has linear complexity (the compiler is not forced to do the computation in compile time, and code optimization is poor in MSVC). Clang and gcc compiles a return 20;.

    And this is how ctMap[404] works (with the same three compilers):

    • constexpr int C = ctMap[404]; – Does not compile, as mentioned above.
    • int Foo() { return ctMap[404]; } – The same remarks apply as for ctMap[10], but Foo will return 0. You cannot know, that 404 was not in the map. To get the compilation error, Foo has to be constexpr and forced to be evaluated in compile time by e.g. assigning it to a constexpr variable or an enumerator, using it in a template argument, as a size of a C array, in a static_assert, etc.