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

Question

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 :)

Recitative

The consts need to be constexpr – Copro

there are many reasons why this won't work: 1) memory allocation is prohibited in constexpr because you can't allocate memory when there's no allocator running. That means no string, vector or any container mapping. Probably OK for mapping int to int, but then you'll face another issue: 2) C++11's constexpr is extremely limited and allows only very simple expressions without any local variables. You need at least C++17 to have some better metaprogramming experience – Alter

Answer 1

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.

Chaplin

this "map" looks a value up in O(n) which isn't a real map at all – Alter

unfortunately im using IAR compiler (Embedded code) and at the moment only c++11 is supported :( – Recitative

can you help me change your implementation to recursive one (support c++ 11 ?) also - can we avoid exception throwing (shudn't be used in embedded) – Recitative

@Alter it’s O(1) at runtime though, isn’t it? – Dynamoelectric

I edited the answer to address the above topics. The O(n) or O(1) complexity is explained, the solution is now in C++11 without exceptions, although I kept a link to the C++14 version. – Chaplin

Thank you so much. I think this module is extremely useful (when used write with constexpr) – Recitative

As you mentioned above - if the consexpr keyword is only a compiler recommendation to calcule in compilation time (but not forced to).. How can i even know if these calculations were made in compile time or runtime? – Recitative

@RoiT7: In certain situations the calculated value is needed during compilation. That's when the compiler is forced to do it in compile time (e.g. in template parameters or in static_assert, and I don't know where else). In other places I think, the language does not mandate compile time evaluation, so it's up to the code optimizer, whether it substitutes the calculated value or not. I don't know where these places are (I am writing from experience, not from the knowledge of the standard), but where it is up to the optimizer, you cannot know what will be the result of the optimization. – Chaplin

Answer 2

A few things to note here, if you want to do this properly: (a) the only variable-sized data structure available to you as a language primitive are parameter packs, which are functionally linked lists - accessing the head is O(1), looking up an arbitrary element is O(N). (b) however, you can implement a binary search tree given a node template that takes 3 parameters: a key-value pair, a left node if any, and a right node if any. You can use void to represent lack of left or right children. (c) then you want to change your type-level constructor to a metafunction that actually sorts the input parameter pack before you build your tree. (d) the correct sorting algorithm is merge sort which can efficiently be implemented on tapes so it also works for linked lists; however this can be a bit tricky to see how to do with templates.

I have a very heavily-commented open-source (LGPL) implementation of a compile-time merge sort + BST-based compile-time map here: https://github.com/Geopipe/Cxx-Heterogeneous-Maps/blob/master/include/hmap/hmap.hpp

I was targeting C++17, but that's mostly because of the shenanigans required to use string literal keys, if you're using integers as keys that should be a lot less messy. It also allows for run-time mutation of values but compile-time detection of whether they are present or not, and heterogeneous value types and provides a compile error if a key is missing or referencing the wrong type. Should be straightforward to modify to your needs and get lower compile-time algorithmic complexity than the linear search in the currently accepted answer.

Yearround