Lookup Table with Constexpr

Lookup table with constexpr

I'll dump the code first, adding references and comments where necessary/appropriate later. Just leave a comment if the result is somewhat close to what you're looking for.

Indices trick for pack expansion (required here to apply the generator), by Xeo, from this answer, modified to use std::size_t instead of unsigned.

#include <cstddef>

// by Xeo, from https://stackoverflow.com/a/13294458/420683
template<std::size_t... Is> struct seq{};
template<std::size_t N, std::size_t... Is>
struct gen_seq : gen_seq<N-1, N-1, Is...>{};
template<std::size_t... Is>
struct gen_seq<0, Is...> : seq<Is...>{};

Generator function:

#include <array>

template<class Generator, std::size_t... Is>
constexpr auto generate_array_helper(Generator g, seq<Is...>)
-> std::array<decltype(g(std::size_t{}, sizeof...(Is))), sizeof...(Is)>
{
    return {{g(Is, sizeof...(Is))...}};
}

template<std::size_t tcount, class Generator>
constexpr auto generate_array(Generator g)
-> decltype( generate_array_helper(g, gen_seq<tcount>{}) )
{
    return generate_array_helper(g, gen_seq<tcount>{});
}

Usage example:

// some literal type
struct point
{
    float x;
    float y;
};
// output support for `std::ostream`
#include <iostream>
std::ostream& operator<<(std::ostream& o, point const& p)
{  return o << p.x << ", " << p.y;  }

// a user-defined generator
constexpr point my_generator(std::size_t curr, std::size_t total)
{
    return {curr*40.0f/(total-1), curr*20.0f/(total-1)};
}

int main()
{
    constexpr auto first_array = generate_array<5>(my_generator);
    constexpr auto second_array = generate_array<10>(my_generator);

    std::cout << "first array: \n";
    for(auto p : first_array)
    {
        std::cout << p << '\n';
    }
    std::cout << "========================\n";

    std::cout << "second array: \n";
    for(auto p : second_array)
    {
        std::cout << p << '\n';
    }
}

Compile-Time Lookup-Table with initializer_list

@Barry's answer pinpointed me in the right direction. Always explicitly listing pair in the list is undesirable. Moreover, I want to be able to partially specialize the template argument list of map. Consider the following example:

// for the sake of the example, suppose this works
constexpr map n({{1, "1"}, {2, "2"}});
              // -> decltype(n) == map<int, const char*, 2>

// the following won't work
constexpr map<std::size_t, const char*> m({{1, "1"}, {2, "2"}});

However, perhaps the user wants that the map contains std::size_t as key, which does not have a literal. i.e. s/he would have to define a user-defined literal just to do that.

We can resolve this by offloading the work to a make_map function, allowing us to partially specialize the map:

// deduction guide for map's array constructor
template<class Key, class Value, std::size_t Size>
map(cxpair<Key, Value>(&&)[Size]) -> map<Key, Value, Size>;

// make_map builds the map
template<typename Key, typename Value, std::size_t Size>
constexpr auto make_map(cxpair<Key, Value>(&&m)[Size]) -> map<Key, Value, Size>
{ return map<Key, Value, Size>(std::begin(m), std::end(m)); }

// allowing us to do:
constexpr auto mapr = make_map<int, std::string_view>({ {1, "1"},
                                                        {2, "2"},
                                                        {3, "3"} });

Creating a lookup table at compile time

You can use an immediately invoked lambda:

#include <array>

using ResultT = int;
constexpr ResultT f(int i)
{
    return i * 2;
}

constexpr auto LUT = []
{
    constexpr auto LUT_Size = 1024;
    std::array<ResultT, LUT_Size> arr = {};

    for (int i = 0; i < LUT_Size; ++i)
    {
        arr[i] = f(i);
    }

    return arr;
}();

static_assert(LUT[100] == 200);

Modern C++: initialize constexpr tables

Since C++14, for loops are allowed in constexpr functions. Moreover, since C++17, std::array::operator[] is constexpr too.

So you can write something like this:

template<class T, size_t N, class F>
constexpr auto make_table(F func, T first)
{
    std::array<T, N> a {first};
    for (size_t i = 1; i < N; ++i)
    {
        a[i] = func(a[i - 1]);
    }
    return a;
}

Example: https://godbolt.org/g/irrfr2

C++ constexpr array lookup: memory overhead? Other gotchas?

If you call a constexpr function with a non-constant expression, it will call the function at run time.

If you call getStruct with a constant expression, the compiler can just call the function at compile time. Then, the getStruct function will be "unused" at runtime, and the compiler will probably optimise it out. At this point, myMap will also be unused, and be optimised out.

In terms of runtime size, it would actually probably be smaller than an std::unordered_map or std::map; It literally stores the minimum information necessary. But it's lookup time would be a lot slower, as it has to compare all the elements individually in O(N) time, so it doesn't actually do what a map does (reduce lookup time).

If you want to make it more likely that it is optimised out, I would ensure that it is only used in constant-expression situations:

template<MyEnum key>
struct getStruct
{
    static constexpr const MyStruct value = _getStruct(key);
}

Here's some compiler output that shows that the map is optimised out entirely

And about including it in multiple translation units, it would be duplicated in every one since you use an anonymous namespace to define it. If it was optimised out in all of them, there would be no overhead, but it would still be duplicated for every translation unit that you do a runtime lookup in.

---

Related Topics